季夢(mèng)清

摘要：傳統(tǒng)的CSD集中式算法因?yàn)榭紤]較為單一，所產(chǎn)生的CDS不夠穩(wěn)定。針對(duì)這個(gè)問(wèn)題，設(shè)計(jì)實(shí)現(xiàn)了對(duì)應(yīng)的CDS分布式算法，并從節(jié)點(diǎn)剩余能量，度以及ID三方面進(jìn)行節(jié)點(diǎn)選取。通過(guò)對(duì)比實(shí)驗(yàn)，從形成的CDS大小，網(wǎng)絡(luò)生命周期等方面，驗(yàn)證了CDS分布式算法的有效性。

關(guān)鍵詞： Ad hoc網(wǎng)絡(luò)；虛擬骨干網(wǎng)；連通支配集；分布式算法

中圖分類號(hào)：TP393.08 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1009-3044（2016）02-0178-03

Abstract： Existing CSD distributed algorithms for generating CSD consider singlely so that the generated CSD is not stable enough. In order to solve this problem， the distributed algorithm for generating CSD in this paper combines with residual energy， degree and ID to select node in CSD. Experiments show that the proposed method can achieve the desired effect from the aspects of the size of CSD and life cycle of network.

Key words： Ad hoc network； virtual backbone； connected dominating set； distributed algorithm

1 引言

目前，無(wú)線局域網(wǎng)（IEEE802.11和HiperLAN）、蜂窩數(shù)字式分組數(shù)據(jù)交換網(wǎng)（CDPD）、家庭無(wú)線網(wǎng)（Home RF）、藍(lán)牙 （Bluetooth）[1]等新移動(dòng)通信技術(shù)的相繼涌現(xiàn)，并且無(wú)線通信網(wǎng)絡(luò)在全球范圍內(nèi)都已經(jīng)被廣泛地使用。它們的運(yùn)行通常要基于事先架設(shè)的網(wǎng)絡(luò)基礎(chǔ)設(shè)施，當(dāng)災(zāi)難發(fā)生，網(wǎng)絡(luò)設(shè)備被毀壞時(shí)，這些網(wǎng)絡(luò)完全無(wú)法工作。此時(shí)我們需要一種能夠快速自動(dòng)組網(wǎng)的臨時(shí)的移動(dòng)通信技術(shù)，也就是Ad hoc網(wǎng)絡(luò)技術(shù)[2，3]。它是一種無(wú)線通信網(wǎng)絡(luò)，其特點(diǎn)為無(wú)中心、多跳、自組織[4]，整個(gè)網(wǎng)絡(luò)沒(méi)有固定的基礎(chǔ)設(shè)施，每個(gè)節(jié)點(diǎn)都能以任意方式動(dòng)態(tài)地保持與其他節(jié)點(diǎn)的聯(lián)系，并且都是移動(dòng)的。

在Ad hoc網(wǎng)絡(luò)中的移動(dòng)節(jié)點(diǎn)都同時(shí)擔(dān)當(dāng)著主機(jī)和獨(dú)立路由的雙重功能，但節(jié)點(diǎn)在能量供應(yīng)、網(wǎng)絡(luò)帶寬、計(jì)等各方面都有制約，因此我們需要綜合各節(jié)點(diǎn)的資源選取出骨干節(jié)點(diǎn)用于承擔(dān)網(wǎng)絡(luò)的通信。關(guān)于骨干節(jié)點(diǎn)的選取，目前主要的方法有CDS算法[3]，主要分為兩類：集中式，分布式。集中式算法需要用到整個(gè)網(wǎng)絡(luò)的拓?fù)湫畔?，這對(duì)于缺乏中心控制的Ad hoc網(wǎng)絡(luò)來(lái)說(shuō)是難以實(shí)現(xiàn)的，因此我們就要引入CDS集中式算法的分布版本。它只需要相鄰節(jié)點(diǎn)之間的信息即可獲得骨干網(wǎng)，不過(guò)由于它應(yīng)用的是相鄰節(jié)點(diǎn)之間的信息。根據(jù)節(jié)點(diǎn)的能量，度等選舉出Ad hoc網(wǎng)絡(luò)當(dāng)中的骨干節(jié)點(diǎn)，使得網(wǎng)絡(luò)的網(wǎng)絡(luò)能量消耗達(dá)到平衡，延長(zhǎng)網(wǎng)絡(luò)的壽命。又由于集中式算法需要全局拓?fù)湫畔㈦y以實(shí)現(xiàn)，所以有實(shí)現(xiàn)CDS分布式算法的必要。

CDS分布式算法[5-7]由于其現(xiàn)實(shí)意義成為了當(dāng)前研究的熱點(diǎn)。文獻(xiàn)[7]的算法，唯一的ID是區(qū)別每個(gè)節(jié)點(diǎn)的標(biāo)志。由于算法對(duì)于節(jié)點(diǎn)的選擇因素考慮比較單一，所以產(chǎn)生的CDS相對(duì)較大，且有巨大的維護(hù)開銷將被花費(fèi)在從根節(jié)點(diǎn)出發(fā)形成生成樹的過(guò)程當(dāng)中。因此，在本文算法中我們綜合考慮各方面的關(guān)鍵因素，將節(jié)點(diǎn)剩余能量，度等作為選擇CSD節(jié)點(diǎn)的標(biāo)準(zhǔn)，使得生成的CSD能夠盡可能的穩(wěn)健。

2 分布式CDS算法

本文將連通支配集分布式算法簡(jiǎn)稱為CDS-D算法。本算法是對(duì)CDS集中式算法的分布式版本，只利用相鄰節(jié)點(diǎn)即一跳節(jié)點(diǎn)之間的信息進(jìn)行實(shí)現(xiàn)與維護(hù)，大致分為節(jié)點(diǎn)分層，節(jié)點(diǎn)染色以及優(yōu)化三個(gè)階段。

在算法中的被支配節(jié)點(diǎn)的顏色為gray或者white，支配節(jié)點(diǎn)的顏色為black或者blue，本算法初始狀態(tài)每個(gè)節(jié)點(diǎn)的顏色為white，并根據(jù)算法成為black或者gray節(jié)點(diǎn)。blue節(jié)點(diǎn)只能由gray轉(zhuǎn)化而來(lái)，并且不能再改變。每個(gè)節(jié)點(diǎn)顏色變化后都要與相鄰節(jié)點(diǎn)廣播自己的狀態(tài)。算法所運(yùn)用的規(guī)則如下所示：

rule 1 當(dāng)某個(gè)節(jié)點(diǎn)變?yōu)橹涔?jié)點(diǎn)，則將其周圍一跳非支配（white或者gray）鄰節(jié)點(diǎn)染為gray。

rule 2 根節(jié)點(diǎn)將自己染為black。

rule 3 對(duì)于節(jié)點(diǎn)x，如果自己的父節(jié)點(diǎn)或者比自己權(quán)重更大的兄弟節(jié)點(diǎn)中存在支配節(jié)點(diǎn)，則x保持原狀態(tài)不變。

2.1 節(jié)點(diǎn)分層

（1）選擇根節(jié)點(diǎn)r。

（2）利用分布式BFS算法將所有節(jié)點(diǎn)分成不同的等級(jí)。

（3）令數(shù)組V[k][] = {y ∈v | hopdist（r， y） = k}表示與根節(jié)點(diǎn)最短跳數(shù)為k的節(jié)點(diǎn)的集合。

顯然k的最小值為0，可能的最大值為總節(jié)點(diǎn)數(shù)N-1；

當(dāng)k = 0時(shí)，V[k][]中只放入根節(jié)點(diǎn)r，k=k+1，并對(duì)所有根節(jié)點(diǎn)的鄰節(jié)點(diǎn)進(jìn)行廣播，即此時(shí)節(jié)點(diǎn)r為他們的父節(jié)點(diǎn)；

當(dāng)k = 1時(shí)，V[k][] = { y∈v| hopdist （r， y） = 1}，即與根節(jié)點(diǎn)r相鄰的所有節(jié)點(diǎn)，根據(jù)V[0][]與V[1][]確定出V[1][]層所有節(jié)點(diǎn)的父節(jié)點(diǎn)與兄弟節(jié)點(diǎn)，并對(duì)其進(jìn)行廣播，k = k+1；

當(dāng)k>=2且k<=N-1時(shí)，對(duì)于任意的節(jié)點(diǎn)x∈V[k-1][]，對(duì)其進(jìn)行如下操作：{y∈v| hopdist（x， y） = 1}-{a∈v| hopdist（x， a） = 1&&a∈V[k-1][]}- {b∈v| hopdist（x ，b） = 1&&b∈V[k-2][]}，即從x的所有相鄰節(jié)點(diǎn)中除去位于V[k-1][]層與V[k-2][]的節(jié)點(diǎn)即為與x相鄰的V[k][]層中的頂點(diǎn)集合，根據(jù)V[k-1][]與V[k-2][]確定出V[k][]層所有節(jié)點(diǎn)的父節(jié)點(diǎn)與兄弟節(jié)點(diǎn)，并對(duì)其進(jìn)行廣播，對(duì)V[k-1][]層中的每個(gè)節(jié)點(diǎn)進(jìn)行上述操作，便可得到V[k][]中的所有節(jié)點(diǎn)，k = k+1。