一種基于分布式CDS的Adhoc網絡方法

季夢清

摘要：傳統的CSD集中式算法因為考慮較為單一，所產生的CDS不夠穩定。針對這個問題，設計實現了對應的CDS分布式算法，并從節點剩余能量，度以及ID三方面進行節點選取。通過對比實驗，從形成的CDS大小，網絡生命周期等方面，驗證了CDS分布式算法的有效性。

關鍵詞： Ad hoc網絡；虛擬骨干網；連通支配集；分布式算法

中圖分類號：TP393.08 文獻標識碼：A 文章編號：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 引言

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

在Ad hoc網絡中的移動節點都同時擔當著主機和獨立路由的雙重功能，但節點在能量供應、網絡帶寬、計等各方面都有制約，因此我們需要綜合各節點的資源選取出骨干節點用于承擔網絡的通信。關于骨干節點的選取，目前主要的方法有CDS算法[3]，主要分為兩類：集中式，分布式。集中式算法需要用到整個網絡的拓撲信息，這對于缺乏中心控制的Ad hoc網絡來說是難以實現的，因此我們就要引入CDS集中式算法的分布版本。它只需要相鄰節點之間的信息即可獲得骨干網，不過由于它應用的是相鄰節點之間的信息。根據節點的能量，度等選舉出Ad hoc網絡當中的骨干節點，使得網絡的網絡能量消耗達到平衡，延長網絡的壽命。又由于集中式算法需要全局拓撲信息難以實現，所以有實現CDS分布式算法的必要。

CDS分布式算法[5-7]由于其現實意義成為了當前研究的熱點。文獻[7]的算法，唯一的ID是區別每個節點的標志。由于算法對于節點的選擇因素考慮比較單一，所以產生的CDS相對較大，且有巨大的維護開銷將被花費在從根節點出發形成生成樹的過程當中。因此，在本文算法中我們綜合考慮各方面的關鍵因素，將節點剩余能量，度等作為選擇CSD節點的標準，使得生成的CSD能夠盡可能的穩健。

2 分布式CDS算法

本文將連通支配集分布式算法簡稱為CDS-D算法。本算法是對CDS集中式算法的分布式版本，只利用相鄰節點即一跳節點之間的信息進行實現與維護，大致分為節點分層，節點染色以及優化三個階段。

在算法中的被支配節點的顏色為gray或者white，支配節點的顏色為black或者blue，本算法初始狀態每個節點的顏色為white，并根據算法成為black或者gray節點。blue節點只能由gray轉化而來，并且不能再改變。每個節點顏色變化后都要與相鄰節點廣播自己的狀態。算法所運用的規則如下所示：

rule 1 當某個節點變為支配節點，則將其周圍一跳非支配（white或者gray）鄰節點染為gray。

rule 2 根節點將自己染為black。

rule 3 對于節點x，如果自己的父節點或者比自己權重更大的兄弟節點中存在支配節點，則x保持原狀態不變。

2.1 節點分層

（1）選擇根節點r。

（2）利用分布式BFS算法將所有節點分成不同的等級。

（3）令數組V[k][] = {y ∈v | hopdist（r， y） = k}表示與根節點最短跳數為k的節點的集合。

顯然k的最小值為0，可能的最大值為總節點數N-1；

當k = 0時，V[k][]中只放入根節點r，k=k+1，并對所有根節點的鄰節點進行廣播，即此時節點r為他們的父節點；

當k = 1時，V[k][] = { y∈v| hopdist （r， y） = 1}，即與根節點r相鄰的所有節點，根據V[0][]與V[1][]確定出V[1][]層所有節點的父節點與兄弟節點，并對其進行廣播，k = k+1；

當k>=2且k<=N-1時，對于任意的節點x∈V[k-1][]，對其進行如下操作：{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的所有相鄰節點中除去位于V[k-1][]層與V[k-2][]的節點即為與x相鄰的V[k][]層中的頂點集合，根據V[k-1][]與V[k-2][]確定出V[k][]層所有節點的父節點與兄弟節點，并對其進行廣播，對V[k-1][]層中的每個節點進行上述操作，便可得到V[k][]中的所有節點，k = k+1。