楊陽，芮蘭蘭，郭少勇，邱雪松，亓峰

(北京郵電大學 網(wǎng)絡(luò)與交換技術(shù)國家重點實驗室，北京 100876)

1 引言

移動自組織網(wǎng)絡(luò)(MANET)旨在建立一種無需固定設(shè)施便可即時組網(wǎng)、隨時通信的數(shù)據(jù)網(wǎng)絡(luò)。這要求設(shè)計的路由算法必須具備收斂快、自適應(yīng)、高效能等特性。洪泛路由模式雖然簡單，但會導(dǎo)致網(wǎng)絡(luò)數(shù)據(jù)的高冗余，甚至廣播風暴[1]。基于最小連通支配集(MCDS, minimum connected dominating set)的分層路由模式將路由過程簡化到 MCDS生成的較小子網(wǎng)，構(gòu)成高一級的虛擬骨干網(wǎng)，負責路由計算和維護，大幅提高路由效率。然而，MANET拓撲結(jié)構(gòu)的頻繁變動使虛擬骨干網(wǎng)逐步分崩離析，導(dǎo)致路由過程發(fā)生擁塞甚至不可達，嚴重影響通信質(zhì)量。因此，有效的MCDS算法必須隨時適應(yīng)拓撲變化，快速構(gòu)建和恢復(fù)虛擬骨干網(wǎng)，增強路由頑健性。

MCDS屬于NP-C問題[2]，因此在實際應(yīng)用中常使用近似算法，包括集中式算法和分布式算法。集中式算法需要全局拓撲信息，雖能生成較小的連通支配集(CDS)，但不適合多數(shù)無線應(yīng)用，如Greedy算法[3]；分布式算法通過節(jié)點信息交換、協(xié)商等機制構(gòu)造CDS，符合MANET的自組織特性。Dai等人提出了基于剪枝的Rule k算法[4]，Vahid等人擴展出高效的Pruning算法[5]，Rajiv等人提出了基于協(xié)作覆蓋的算法[6]。文獻[7～16]通過圖論建立數(shù)學模型，應(yīng)用聚簇、斯特納樹、獨立集、弱連通支配集、最小權(quán)值連通支配集等概念，研究MANET的連通性問題?，F(xiàn)有研究成果主要根據(jù)特定需求生成CDS，大多忽視MANET拓撲的動態(tài)性，對如何維持虛擬骨干網(wǎng)討論較少，限制了算法適用范圍。

本文針對節(jié)點頻繁移動的大規(guī)模 MANET環(huán)境，提出了基于計時器的 CDS生成算法(TB-CDS,timer based-CDS)，利用節(jié)點計時器的超時機制控制信息交換、環(huán)境感知，并運用啟發(fā)式分簇策略進行網(wǎng)絡(luò)邏輯分區(qū)，實現(xiàn)動態(tài)拓撲下虛擬骨干網(wǎng)的并行構(gòu)建與重構(gòu)，具有較廣泛的普遍通用性。

2 TB-CDS算法

2.1 問題描述和相關(guān)定義

假設(shè)MANET有n個無線節(jié)點，每個節(jié)點有唯一的標識ID，信號覆蓋半徑為r，在此距離內(nèi)無線節(jié)點間是連通的。為優(yōu)化網(wǎng)絡(luò)的資源分配和路由效率，考慮如何利用節(jié)點計時器更新環(huán)境信息，使這n個節(jié)點通過協(xié)商，陸續(xù)加入不同區(qū)域，分布式地選取若干節(jié)點組成虛擬骨干網(wǎng)，并根據(jù)不同拓撲變化調(diào)整骨干網(wǎng)，維持其連通性。

定義1 圖的相關(guān)定義

無向圖 G=(V,E,d)為單位圓圖，其中，V和 E分別代表頂點集和邊集。記N(u)={v|(u, v)∈E}為節(jié)點u的鄰居集；d表示以V中頂點為圓心的圓的半徑，若邊(u, v)∈E，則頂點u, v間的距離|u?v|≤d。以下將無向圖G=(V,E,d)簡稱為圖G=(V,E)。

定義2 最小連通支配集

圖G=(V,E)，CV?，若?u∈V?C，都?v∈C，(u,v)∈E，則稱v為支配節(jié)點，C為G的支配集。若由支配集C導(dǎo)出的子圖是連通圖，稱C為連通支配集(CDS)，節(jié)點最少的連通支配集稱為最小連通支配集(MCDS)，CDS中的節(jié)點組成虛擬骨干網(wǎng)。

定義3 節(jié)點的屬性定義

任意節(jié)點v的標識ID記為nid(v)；簇(區(qū)域)號:aid(v)；度為δ(v)；角色為role(v)=Enum{newcomer,dominatee, dominator}。節(jié)點 v沒有加入?yún)^(qū)域?role(v) =newcomer(新節(jié)點)。節(jié)點v已加入?yún)^(qū)域但不屬于支配集?role(v)= dominatee(被支配節(jié)點)。節(jié)點v已加入?yún)^(qū)域且屬于支配集?role(v)= dominator (支配節(jié)點)。節(jié)點v是初始簇頭(區(qū)域發(fā)起者)?role(v) =dominator，aid(v)= nid(v)。

定義4 節(jié)點的基本信息定義

任意節(jié)點v的基本信息記為Info(v)={nid(v), aid(v),role(v), δ(v)}。若 role(v)≠ newcomer，則它的異簇鄰居集記為 S(v)={u| u∈N(v)∧ aid(u)≠ aid(v)∧ role(u)≠ newcomer}，異簇鄰居信息集記為SN(v)= {Info(u)|u∈ S(v)}。

定義5 節(jié)點的消息定義

節(jié)點發(fā)送 4 種消息:Status，JoinArea，AllyArea，BeaconArea。其中，Status(Info(v),SN(v)(可選))，用于節(jié)點 v周期性廣播自身狀態(tài)；JoinArea(Info(u),Info(v))用于節(jié)點u聲明以節(jié)點v為接入點加入v所在區(qū)域；AllyArea(Info(u),Info(v))用于節(jié)點u申請與異簇節(jié)點 v連通所屬區(qū)域的骨干網(wǎng)；Beacon Area(Info(v), t)，用于初始簇頭v周期性廣播區(qū)域生存消息，其中，t為節(jié)點v發(fā)送消息的時間戳，它由該區(qū)域內(nèi)的dominator節(jié)點多跳轉(zhuǎn)發(fā)。

定義6 節(jié)點的計時器定義

節(jié)點使用2種計時器:SendTimer、RecvTimer。分別控制消息發(fā)送和接收，都能引發(fā)超時事件。如節(jié)點u啟動SendTimer(Status)，將周期性廣播Status(Info(u))；啟動 RecvTimer(Status(Info(v)))，監(jiān)控鄰居v的生存。

2.2 算法步驟

TB-CDS算法分為三階段:階段一，在計時器控制下，鄰居節(jié)點交換信息，利用啟發(fā)式方法選舉初始簇頭，聲明各自區(qū)域；階段二，節(jié)點選擇接入節(jié)點，陸續(xù)加入不同區(qū)域，分布式地構(gòu)建以初始簇頭為根節(jié)點的域內(nèi) CDS生成樹；階段三，通過調(diào)整邊界節(jié)點連通相鄰區(qū)域的 CDS生成樹，完成虛擬骨干網(wǎng)的構(gòu)建。計時器的超時機制使節(jié)點能夠感知拓撲環(huán)境變化，實現(xiàn)虛擬骨干網(wǎng)的拓撲重構(gòu)。假設(shè)的MANET由圖G=(V,E)表示。

階段Ⅰ 基于啟發(fā)式策略的分區(qū)

1) 所有節(jié)點 u∈V 設(shè)置 role(u)←newcomer，aid(u)←nid(u)，δ(u)←0，完成初始化；

2) 所有節(jié)點 u∈V開啟計時器 SendTimer(Status)，周期性廣播Status(Info(u))，進行鄰居發(fā)現(xiàn)；

3) 節(jié)點間接收鄰居Status，更新自身Info,存儲鄰居 Info。若首次發(fā)現(xiàn)鄰居 v，則啟動 RecvTimer(Status(Info(v)))，否則予以重置；

4) 2次Status廣播后，每個節(jié)點u∈V能夠獲取1跳內(nèi)鄰居的最新Info；

5) 每個newcomer節(jié)點u∈V，若N(u)≠?，則進行初始簇頭選舉。選舉的優(yōu)先級序列設(shè)為P(v)=(role(v),δ(v),nid(v))，并規(guī)定 P(v)＞P(u) (v≠ u)，當且僅當滿足下列任意條件時成立

計算 MaxP(u)=Max({ P(v)| v∈N(u) })；若P(u)＞Max?P(u)，則繼續(xù) 6)；若 P(u)＜MaxP(u)=P(v)，其中，role(v)=newcomer，則轉(zhuǎn)到 7)，role(v)=dominator或dominatee，則轉(zhuǎn)到8)；

6) 此newcomer節(jié)點u自選舉為初始簇頭，設(shè)置 role(u)←dominator，開啟 SendTimer(Beacon Area)，周期性廣播 BeaconArea(Info(u),t0)，區(qū)域號設(shè)為aid(u)；繼續(xù)7)；

在階段Ⅰ中，由于節(jié)點標識符nid的唯一性，不同節(jié)點的優(yōu)先級序列P必不等，因此一定能選舉出若干初始簇頭。節(jié)點的role越大、δ越大，覆蓋節(jié)點越多，選舉優(yōu)先級P就越高，有利于縮小CDS。

階段Ⅱ 區(qū)域CDS的生成

7) 每個newcomer節(jié)點u∈V，繼續(xù)接收Status，更新鄰居的Info；轉(zhuǎn)到5)；

8) 若 newcomer節(jié)點 u∈V計算得 P(u)＜MaxP(u)=P(v)，role(v)= dominatee或 dominator，設(shè)置 aid(u)←aid(v)，role(u)←dominatee。向節(jié)點 v發(fā)送 Join-Area(Info(u),Info(v))，表明已加入v所屬區(qū)域aid(v)，并啟動RecvTimer(BeaconArea)，監(jiān)測區(qū)域存活；

9) 若 dominator節(jié)點 v∈V收到 JoinArea(Info(u),Info(v))，順帶更新Info(u)；若為dominatee節(jié)點v，則設(shè)置role(v)←dominator，順帶更新Info(u)；

10) 每個dominator節(jié)點u∈V都維護一個時間戳 T來判斷 BeaconArea(Info(v),t0)消息是否過時。若T＜t0，則廣播轉(zhuǎn)發(fā)，設(shè)置T←t0，重置RecvTimer(BeaconArea)；繼續(xù) 11)。

每個newcomer節(jié)點總能在有限時間內(nèi)，自選舉為初始簇頭dominator，或選擇鄰居dominatee、dominator節(jié)點作為接入點(父節(jié)點)加入?yún)^(qū)域。每個初始簇頭都以自身為根節(jié)點構(gòu)建 CDS生成樹，吸納newcomer節(jié)點加入?yún)^(qū)域。其中，dominator節(jié)點為枝干節(jié)點(虛擬骨干網(wǎng))，dominatee節(jié)點為葉子節(jié)點，伴隨樹的“生長”，覆蓋的節(jié)點逐漸增多，區(qū)域范圍不斷擴大。

階段Ⅲ 區(qū)域邊界的調(diào)整

11) 每個dominatee或dominator節(jié)點u∈V，若處于區(qū)域邊界，則廣播 Status(Info(u),SN(u))。因此可獲得2跳內(nèi)的異簇節(jié)點信息，用于計算是否連通相鄰區(qū)域。設(shè)節(jié)點(v,w)代表連通區(qū)域A與B的邊界網(wǎng)關(guān)組合，MaxR(A,B)=Max({R(v,w)|aid(v)=A∧aid(w)=B∧(v,w)∈E})代表優(yōu)先級最高的組合；網(wǎng)關(guān)組合的優(yōu)先級序列為R(v,w)=(role(v), role(w), nid(v),nid(w))，其中，v∈S(w)且aid(v)＜aid(w)，并規(guī)定R(v,w)＞R(x,y)，當且僅當滿足下列任意條件時成立

若節(jié)點u計算得MaxR(aid(u), aid(v))=R(u,v)，則繼續(xù)12)，否則周期性計算MaxR；

12) 此節(jié)點 u向節(jié)點 v發(fā)送 AllyArea(Info(u),Info(v))，申請連通節(jié)點v所在區(qū)域的CDS；節(jié)點v收到此消息后回復(fù)AllyArea(Info(v),Info(u))，表明同意連通。雙方收到對方發(fā)送的AllyArea后，若role= dominatee，則設(shè)置 role←dominator。

根據(jù)優(yōu)先級序列R的定義，aid較小的節(jié)點總是首先發(fā)送AllyArea；2個dominator節(jié)點的組合將優(yōu)先成為邊界網(wǎng)關(guān)節(jié)點。最后，當所有節(jié)點的role不再改變時，算法達到收斂，網(wǎng)絡(luò)趨于穩(wěn)定，所有區(qū)域的CDS連通成全局CDS，構(gòu)成虛擬骨干網(wǎng)。

上述算法及步驟對應(yīng)的偽碼如圖1和圖2所示。

圖1 偽碼1任意節(jié)點u的狀態(tài)處理線程

圖2 偽碼2任意節(jié)點u的消息處理線程

階段Ⅰ Ⅱ Ⅲ中的計時器超時處理

a) 若節(jié)點u∈V的RecvTimer(Status(Info(v)))超時，則刪除鄰居節(jié)點 v的信息，更新 N(u)后，若N(u)=?，則刪除所有計時器，轉(zhuǎn)到1）后重新初始化為newcomer節(jié)點；

b) 若節(jié)點 u∈V的 RecvTimer(BeaconArea(Info(v),T))超時，則認為已脫離初始簇頭v的管轄，刪除所有計時器，轉(zhuǎn)到2）后重新初始化為new- comer節(jié)點；

c) 若節(jié)點 u∈V的 SendTimer(Status)超時，則廣播Status消息并重置該計時器；

d) 若初始簇頭 u∈V的 SendTimer(Beacon-Area)超時，則廣播 BeaconArea消息并重置該計時器；

拓撲變化可歸結(jié)為節(jié)點撤出和加入或2種動作的組合。節(jié)點撤出發(fā)生于故障、電池耗盡、退出網(wǎng)絡(luò)時，引發(fā)鄰居節(jié)點 RecvTimer (Status)超時，若dominator節(jié)點撤出，可能引發(fā)某些節(jié)點RecvTimer(BeaconArea)超時；節(jié)點加入發(fā)生于加入網(wǎng)絡(luò)、故障恢復(fù)時，將引發(fā)鄰居節(jié)點啟動RecvTimer(Status)。圖3為節(jié)點角色的轉(zhuǎn)換示意，每個節(jié)點在不同階段，根據(jù)拓撲變化、消息交互作出對應(yīng)的角色轉(zhuǎn)換。TB-CDS算法依賴計時器控制節(jié)點進行環(huán)境感知、角色轉(zhuǎn)換，實現(xiàn)虛擬骨干網(wǎng)的自適應(yīng)生成及重構(gòu)。

圖3 節(jié)點的角色轉(zhuǎn)換

2.3 算法應(yīng)用舉例

圖4～圖6描繪了TB-CDS的執(zhí)行過程。

圖 4(a)展示算法的階段Ⅰ，通過計算 MaxP，節(jié)點1、節(jié)點2、節(jié)點3自選舉為初始簇頭。圖4(b)表明階段Ⅱ的開始，向節(jié)點1發(fā)出JoinArea后，節(jié)點 4、節(jié)點 13、節(jié)點 17、節(jié)點 18、節(jié)點 20成為dominatee，加入?yún)^(qū)域A1；節(jié)點6、節(jié)點9、節(jié)點11、節(jié)點16、節(jié)點19加入A2；節(jié)點5、節(jié)點8、節(jié)點14、節(jié)點15、節(jié)點21加入A3。此時節(jié)點22、節(jié)點 23加入網(wǎng)絡(luò)，如圖 4(c)所示。由于 P(v17)=(dominatee,3,17)＞P(v20)=(dominatee,3,20)，節(jié)點 22向節(jié)點17發(fā)送JoinArea后加入A1。圖5(a)展示了階段Ⅲ的開始，邊界節(jié)點5、節(jié)點7、節(jié)點12、節(jié)點15計算MaxR(A1,A3)，獲知邊界網(wǎng)關(guān)僅有2種組合R(v7,v15)＞R(v12,v5)。因此節(jié)點7、節(jié)點15互相發(fā)送AllyArea后成為dominator。同理，邊界節(jié)點9、節(jié)點8、節(jié)點10、節(jié)點13成為dominator，分別連通A2與A3、A2與A1，如圖5(b)，已生成CDS，所有dominator節(jié)點構(gòu)成虛擬骨干網(wǎng)。

圖4 區(qū)域構(gòu)建

此時，節(jié)點9由A2移至A1，無法接收A2內(nèi)的BeaconArea消息，導(dǎo)致RecvTimer(BeaconArea)超時，重新初始化為newcomer。經(jīng)過鄰居發(fā)現(xiàn)，節(jié)點9選擇節(jié)點4作為接入節(jié)點加入A1，節(jié)點4成為dominator。節(jié)點2、節(jié)點8、節(jié)點11、節(jié)點19的RecvTimer(Status (Info(v9)))超時，將刪除節(jié)點9的Info；節(jié)點11計算MaxR(A2,A3)得知R(v11,v8)的優(yōu)先級最高，向節(jié)點8發(fā)送AllyArea并收到回復(fù)后，成為dominator重新連通A2和A3，如圖5(c)所示。

如圖6(a)所示，當節(jié)點7、節(jié)點8故障后，節(jié)點12，5成為dominator，重新連通A1與A3，因為此時的 MaxR(A1,A3)=R(v12,v5)。圖 6(b)中，A3的初始簇頭節(jié)點3發(fā)生故障，導(dǎo)致節(jié)點5、節(jié)點14、節(jié)點15、節(jié)點21的RecvTimer (BeaconArea)超時，全都初始化為 newcomer。調(diào)整后的穩(wěn)定拓撲如圖6(c)所示，節(jié)點14選舉為新的初始簇頭，虛擬骨干網(wǎng)完成重構(gòu)。

2.4 算法正確性證明

定理 1 若初始網(wǎng)絡(luò)是連通的，當所有節(jié)點的role不再改變，區(qū)域邊界通過 dominator節(jié)點連通時，網(wǎng)絡(luò)拓撲達到穩(wěn)定狀態(tài)。

證明 初始時，每個節(jié)點都是newcomer，經(jīng)過2輪Status廣播，能獲取鄰居的最新Info，經(jīng)過計算選舉優(yōu)先級MaxP，必然有m個節(jié)點能成為初始簇頭，m＞0。設(shè)當前時刻為t，節(jié)點變更role和連通區(qū)域等操作所需的時間上限為 T，總節(jié)點數(shù)為 n(n＞m)，剩余newcomer節(jié)點數(shù)量為n?m，那么在至多t+(n?m)T時刻，這些節(jié)點將全部加入到m個區(qū)域中。在t+(n?m)T+T時刻前，區(qū)域邊界必能連通，網(wǎng)絡(luò)拓撲達到穩(wěn)定狀態(tài)。

ATT7022B采用QFP44封裝，內(nèi)部集成了多個適于電信號采集、變換，能對電能、電功率、電流有效值、電壓有效值、功率因數(shù)、頻率等參數(shù)進行精確計算。采樣信號由電流信道和電壓信道進入，經(jīng)過AD轉(zhuǎn)換之后送到數(shù)字信號處理模塊中，數(shù)字信號處理模塊對采集來的數(shù)據(jù)進行運算處理之后，可以得到全波、基波和諧波的有功、無功、視在功率，有功、無功能量，電流、電壓有效值，頻率、功率因數(shù)、相角等參數(shù)[2-3]。

引理 1 若初始網(wǎng)絡(luò)是連通的，則穩(wěn)定狀態(tài)下不存在newcomer節(jié)點。

圖5 虛擬骨干網(wǎng)的生成

圖6 虛擬骨干網(wǎng)的重構(gòu)

證明(反證法) 假設(shè)在穩(wěn)定狀態(tài)下存在newcomer節(jié)點，不妨設(shè)為u，由于初始網(wǎng)絡(luò)是連通的，那么u擁有至少一個鄰居節(jié)點v。經(jīng)過有限時間，節(jié)點u將加入某個區(qū)域或自選舉為初始簇頭，role(u)將至少改變一次，與定理1矛盾，得證。

引理 2 每個 dominatee節(jié)點至少與一個dominator節(jié)點相鄰。

證明 區(qū)域 CDS生成樹構(gòu)造過程中，newcomer節(jié)點總是選擇優(yōu)先級最高的鄰居節(jié)點作為接入節(jié)點(父節(jié)點)，成為dominatee，該鄰居節(jié)點則成為dominator。因此，newcomer節(jié)點成為dominatee節(jié)點后，至少與一個dominator節(jié)點相鄰。

引理 3 若初始網(wǎng)絡(luò)是連通的，則穩(wěn)定狀態(tài)下所有dominator節(jié)點構(gòu)成圖G引導(dǎo)的連通子圖。

證明 每個區(qū)域的 dominator節(jié)點為該區(qū)域內(nèi)CDS生成樹的枝干節(jié)點，構(gòu)成圖 G引導(dǎo)的連通子圖。由定理 1，在穩(wěn)定狀態(tài)下，區(qū)域邊界通過dominator節(jié)點連通，因此，所有dominator節(jié)點能構(gòu)成圖G引導(dǎo)的連通子圖。

定理 2 若初始網(wǎng)絡(luò)是連通的，則穩(wěn)定狀態(tài)下所有dominator節(jié)點構(gòu)成CDS，即虛擬骨干網(wǎng)。

2.5 算法性能分析

本節(jié)將在最差情況下，分析TB-CDS算法的時間復(fù)雜度和消息復(fù)雜度。

假設(shè)節(jié)點做出任何決策所需的時間上限為常數(shù)T，節(jié)點廣播Status的周期為Ts, Ts＜T，初始簇頭廣播BeaconArea的周期為TB, TB＜T。如圖7所示，當所有節(jié)點分布于一條直接上，并以nid升序或降序排列時，算法性能最差。節(jié)點2成為初始簇頭。初始簇頭選舉所需的時間上限為T，剩余n?1個節(jié)點加入?yún)^(qū)域所需的時間上限為(n?2)T，因此，構(gòu)建CDS所需時間上限為(n?1)T，算法時間復(fù)雜度為O(n)。設(shè)發(fā)送的 Status數(shù)為 Ms，BeaconArea數(shù)為MB，JoinArea數(shù)為MJ。n個節(jié)點在(n?1)T內(nèi)廣播的Status數(shù)量為

JoinArea數(shù)量為 MJ=n?1～O(n)。BeaconArea由dominator節(jié)點中繼廣播，在構(gòu)建CDS的過程中，dominator節(jié)點的數(shù)量逐步增至n?2個，則

(n?2 個 dominator 節(jié)點在(n?1)×T 時間內(nèi)發(fā)送Beacon Area的數(shù)量)。因此，構(gòu)建CDS所需發(fā)送消息總數(shù)為 M=Ms+MB+MJ～O(n2)。

圖7 最差情況下的拓撲結(jié)構(gòu)

最差情況下，TB-CDS算法的時間復(fù)雜度為O(n)，消息復(fù)雜度為O(n2)。事實上，TB-CDS算法的收斂時間取決于并行構(gòu)建區(qū)域的時間開銷，因此一般情況下的時間復(fù)雜度為O(D)，其中，D為最大區(qū)域的直徑，D通常比n小得多；以下將通過仿真實驗得出，一般情況下的消息復(fù)雜度為O(nlogn)。

3 仿真實驗

本文采用OPNET軟件，模擬擁有n個節(jié)點的MANET網(wǎng)絡(luò)(n取值為40～1000)，隨機部署于100m×100m的矩形監(jiān)測區(qū)域。節(jié)點傳輸功率設(shè)置為3.65 E-6 W和9.25E-7 W，對應(yīng)的通信半徑r分別約為15m和30m；數(shù)據(jù)分組大小設(shè)置為512byte，分組發(fā)送率為1packet/s。實驗針對每種算法，根據(jù)n、r的取值產(chǎn)生300次隨機拓撲結(jié)構(gòu)，統(tǒng)計性能指標(CDS大小、消息開銷、拓撲調(diào)整輪數(shù))，取均值作為仿真結(jié)果。TB-CDS算法中Status的發(fā)送周期Ts和超時期限 Es分別設(shè)置為 1000ms、5000ms；BeaconArea的發(fā)送周期TB和超時期限EB分別設(shè)置為3000ms、9000ms。

本文選取經(jīng)典的Greedy算法[3]和Rule k算法[4]，以及 Pruning算法[5]用于在靜態(tài)拓撲下與 TB-CDS算法比較收斂時的CDS大小、消息開銷這2項基本指標。這 3種算法生成的 CDS大小較為趨近MCDS的近似解，適合多數(shù)算法衡量此項指標。

如圖8(a)、圖8(b)所示，當r=15m，n∈[40,200]時，TB-CDS算法生成的CDS大于Greedy算法的，但遠小于另2種算法，而n∈[200,1000]時，TB-CDS算法逐漸接近Pruning算法，因為區(qū)域數(shù)量的增加導(dǎo)致邊界網(wǎng)關(guān)增多。由圖8(c)、圖8(d)可知，r=30m時，鄰居大量增加使得CDS減小。在n∈[40,200]，Pruning算法比TB-CDS算法稍差，但在n∈[200,1000]稍優(yōu)，因為Pruning算法中每個節(jié)點擁有更多鄰居信息，刪除的冗余節(jié)點也更多，實驗表明，一般情況下TB-CDS算法生成的CDS的大小具備競爭力，在節(jié)點稠密的環(huán)境下更為優(yōu)異。

圖8 不同節(jié)點數(shù)下生成CDS的大小

Greedy算法基于已知拓撲結(jié)構(gòu)，節(jié)點間無需消息交換；Rule k算法與Pruning算法的消息開銷相近，因此只選取TB-CDS算法與Pruning算法比較消息復(fù)雜度。如圖9(a)，2種r下的TB-CDS算法消息數(shù)量接近，小于 Pruning算法；在圖 9(b)中，Pruning消息數(shù)量遠高于TB-CDS算法，因為所有節(jié)點需要獲取兩跳內(nèi)所有鄰居的節(jié)點信息，消息開銷受r影響很大。TB-CDS算法中r的增加使區(qū)域數(shù)量、支配節(jié)點數(shù)減少，降低了維持區(qū)域的消息開銷。實驗表明，一般情況下TB-CDS算法的消息復(fù)雜度為O(nlogn)。

圖9 收斂時已發(fā)送的消息數(shù)量

考察TB-CDS算法在大型網(wǎng)絡(luò)下對拓撲變化的適應(yīng)速度。當算法達到收斂時，計算5%，10%的節(jié)點撤出網(wǎng)絡(luò)、加入網(wǎng)絡(luò)、隨機移動(分別用W, J, M表示)后虛擬骨干網(wǎng)完成重構(gòu)需要幾輪節(jié)點調(diào)整操作(接收消息，更新拓撲信息，優(yōu)先級P, R計算，發(fā)送消息，更改角色)。如圖10所示，同等節(jié)點數(shù)量下，r越大則鄰居節(jié)點越多，調(diào)整輪數(shù)較小。節(jié)點撤出網(wǎng)絡(luò)和發(fā)生移動將影響虛擬骨干網(wǎng)的連通性，相關(guān)節(jié)點的計時器超時后，才開始重構(gòu)骨干網(wǎng)，而新節(jié)點的加入對連通性沒有影響，只需添加骨干網(wǎng)節(jié)點即可恢復(fù)，因此調(diào)整輪數(shù)大大減少。

圖10 拓撲發(fā)生變化后，算法所需調(diào)整輪數(shù)

4 結(jié)束語

本文針對MANET節(jié)點移動較為頻繁的特點，提出基于計時器思想的MCDS生成(TB-CDS)算法，分布式地構(gòu)建虛擬骨干網(wǎng)，解決了維持骨干網(wǎng)連通性的關(guān)鍵問題，實現(xiàn)了動態(tài)拓撲下骨干網(wǎng)的快速重構(gòu)，證明了算法的正確性。仿真結(jié)果表明，TB-CDS算法能以較低的開銷生成較小的虛擬骨干網(wǎng)，不但有效減少了冗余轉(zhuǎn)發(fā)節(jié)點，而且具有良好的自愈能力。由于TB-CDS算法的仿真實驗環(huán)境較為理想，尚缺乏針對終端節(jié)點間差異性的考慮。因此下一步將綜合終端差異性來完善TB-CDS算法，并應(yīng)用于MANET路由協(xié)議，以期作為分層按需路由的基礎(chǔ)。

[1]唐勇, 周明天, 張欣.無線傳感器網(wǎng)絡(luò)路由協(xié)議研究進展[J].軟件學報,2006,17(3):410-421.TANG Y, ZHOU M T, ZHANG X.Overview of routing protocols in wireless sensor networks[J].Journal of Software, 2006, 17(3):410-421.

[2]GAREY M R, JOHNSON D S.Computers and Intractability:A Guide to the Theory of NP-Completeness[M].New York:W H Freeman &Co, 1979.

[3]DAS B, BHARGHAVAN V.Routing in ad-hoc networks using minimum connected dominating sets[A].Proceedings of the IEEE International Conference on Communications[C].Montreal, Canada, 1997.376-380.

[4]DAI F, WU J.An extended localized algorithm for connected dominating set formation in ad hoc wireless networks[J].IEEE Transactions on Parallel and Distributed Systems,2004,15(10):908-920.

[5]VAHID G, SEYED N, MOJTABA M.Connected dominating set construction using an efficient pruning method in ad hoc networks[A].Wireless Internet Conference (IEEE WICON) The 5th Annual ICST[C].Singapore, 2010.1-8.

[6]RAJIV M, CHITTARANJAN M.Minimum connected dominating set using a collaborative cover heuristic for ad hoc sensor networks[J].IEEE Transactions on Parallel and Distributed Systems, 2010, 21(3):292-302.

[7]BO H.Zone-based virtual backbone formation in wireless ad hoc networks[J].Ad Hoc Networks, 2009, 7:183-200.

[8]TORKESTANI J A, MEYBODI M R.An intelligent backbone formation algorithm for wireless ad hoc networks based on distributed learning automata[J].Computer Networks, 2010, 54:826-843.

[9]KIM D Y, ZHANG Z, LI X Y, et al.Better approximation algorithm for computing connected dominating sets in unit ball graphs[J].IEEE Transactions on Mobile Computing, 2010, 9(8):1108-1118.

[10]DING L, GAO X F, WU W L, et al.Distributed construction of connected dominating sets with minimum routing cost in wireless networks[A].Distributed Computing Systems (IEEE ICDCS)[C].Genoa,Italy, 2010.448-457.

[11]WANG Y M, ZHAO D S.A serial MIS based CDS constructing algorithm for wireless networks[A].Green Computing and Communications(GreenCom)IEEE/ACM Int'l Conference on & Int'l Conference on Cyber Physical and Social Computing (CPSCom)[C].Hangzhou,China, 2010, 466-469.

[12]DING L, WU W L, WILLSON J, et al.Efficient algorithms for topology control problem with routing cost constraints in wireless networks[J].IEEE Transactions on Parallel and Distributed Systems,2011, 22(10):1061-1069.

[13]ZHENG C, SUN S X, HUANG T Y.Constructing distributed connected dominating sets in wireless ad hoc and sensor networks[J].Journal of Software, 2011, 22(5):1053-1066.

[14]YINA B, SHI H C, SHANG Y.An efficient algorithm for constructing a connected dominating set in mobile ad hoc networks[J].Journal of Parallel and Distributed Computing, 2011, 77:27-39.

[15]ZOU F, WANG Y X, XU X H, et al.New approximations for mini- mum weighted dominating sets and minimum-weighted connected dominating sets on unit disk graphs[J].Theoretical Computer Science, 2011,412:198-208.

[16]ARIYAM D, CHITTARANJAN M, CHRIS R.An improved greedy construction of CDS in MANET[A].Wireless Communications and Networking Conference (IEEE WCNC)[C].Cancun, Mexico, 2011.790-795.