Ad Hoc分布式虛擬骨干網構建算法＊

狄元博 陶 凱 葉永安

（1.海軍裝備研究院 北京 100161）（2.武漢船舶通信研究所 武漢 430079）（3.73141部隊 南安 362301）

1 引言

現實的分層結構為有線和計算機通信中的網管、資源利用等方面帶來了極大的便利，因此人們期望在Ad Hoc網中也能構建這樣一種骨干網，稱為虛擬骨干網，緩解Ad Hoc自組網因其動態(tài)特性造成的網管和資源利用不便的情況。研究表明，虛擬骨干網在無線自組網的路由、廣播以及連通控制中起著至關重要的作用［1～4］。

單位原模型［5］和圖論中的連通支配集（CDS）模型常被用于Ad Hoc自組網的虛擬骨干網。為了簡化連通控制，總希望找到一個規(guī)模最小的CDS，然而圖論中已經證明，求解最小連通支配集是一個NP完全難題，所以只能用近似的算法求解最小連通支配集［6～9］。

近似算法分為集中式構建算法和分布式構建算法。集中式構建算法需要獲得整個網的拓撲結構，這對成員規(guī)模較大時是一筆不小的開銷。分布式構建算法無線獲得整個網的拓撲結構，具有較好的拓撲動態(tài)適應性。

WAN算法是分布式構造最小連通支配集的典型近似算法之一，本文基于WAN算法［10］提出了一種基于拓撲分層的極小連通支配集的構造算法LMCDS算法，結果顯示LMCDS算法不但可以生成節(jié)點數目較少的連通支配集，而且在消息復雜度方面有明顯改善。

2 LMCDS算法描述

LMCDS算法的流程如圖1所示。在LMCDS算法開始之前，所有節(jié)點需要探索外部的拓撲，其過程如下：所有節(jié)點廣播VISIT訪問消息，消息中附帶其節(jié)點編號。通過接收鄰居節(jié)點的VISIT消息節(jié)點可以構造出鄰居節(jié)點表。而后每個節(jié)點將鄰居節(jié)點表附入VISIT消息中再次廣播，通過接收相鄰節(jié)點發(fā)送的VISIT消息，每個節(jié)點可以計算出鄰居節(jié)點的度（deg）以及鄰居節(jié)點表等信息。所謂節(jié)點的度是指節(jié)點的鄰居節(jié)點的數目，假設網內節(jié)點的最大度為△。

圖1 LMCDS算法流程

2.1 生成樹的構建

構建極大獨立集之前首先要建立一棵生成樹，這樣做的目的是將一個網分為若干層，并確立節(jié)點之間的父子關系。生成樹的構建是通過廣播HELLO消息來實現的。每個節(jié)點都設有一個變量Level，Level初始值均為0。節(jié)點的Level值代表該節(jié)點位于網內的第幾層，即節(jié)點所處層的層號。規(guī)定層號為奇數的為支配層，其余的層為被支配層。廣播HELLO消息的規(guī)則如下

規(guī)則1：選擇節(jié)點號最小的節(jié)點作為根節(jié)點，并將根節(jié)點的Level值設置為1。由根節(jié)點開始廣播HELLO消息，HELLO消息中包含自己的ID和Level值。

規(guī)則2：每個節(jié)點只能接收一次HELLO消息。任意收到HELLO消息的節(jié)點將發(fā)送消息的節(jié)點設置為自己的父節(jié)點，并將自己的Level值設置為發(fā)送節(jié)點Level值加1，然后將自己的ID和Level值添加到HELLO消息中，并轉發(fā)HELLO消息。

規(guī)則3：同時收到HELLO消息的節(jié)點，按時隙轉發(fā)HELLO消息，節(jié)點度大的節(jié)點優(yōu)先轉發(fā)。按時隙轉發(fā)保證了每個節(jié)點只有唯一的父節(jié)點。

當所有節(jié)點的Level值均不為零時，生成樹構建完成。此時，所有節(jié)點的Level值和父節(jié)點都已確定。

2.2 極小支配集的構建

生成樹構建完畢之后，該網隨之分層完畢。接下來開始構建該網的極小支配集。根據圖論的知識，一個圖的極大獨立集（MIS）都是它的極小支配集（MDS），所以可以通過構建MIS的方法實現MDS的構建。

構建MIS開始之前，首先給出一個鍵值（Key）的概念，對任意節(jié)點u，定義其鍵值為 K（u）＝（deg（u），ID（u）），即一個節(jié)點的鍵值是其節(jié)點度與節(jié)點號的有序組合。給定任意兩個節(jié)點u和v，只要deg（u）＞deg（v），則 K（u）＞K（v）；deg（u）＜deg（v），則 K（u）＜K（v）；若 deg（u）＝deg（v），ID（u）＞ID（v），則 K（u）＞K（v）。

LMCDS算法采用染色法構建MIS。初始時所有節(jié)點均為白色，然后按照如下操作逐步對各個節(jié)點進行染色，直至所有的節(jié)點都被染成黑色或灰色，則停止染色。

規(guī)則1：每個支配層首先選擇該層Key值最大的白色節(jié)點并將其染黑。黑色節(jié)點廣播BLACK消息，白色節(jié)點收到BLACK消息就將自己染灰。

規(guī)則2：若支配層中還存在白色節(jié)點就按照規(guī)則1繼續(xù)染色。

規(guī)則3：若支配層無白色節(jié)點，被支配層仍有白色節(jié)點，則從被支配層選擇Key值最大的白色節(jié)點并將其染黑，然后廣播BLACK消息。

染色完成之后，所有的黑色節(jié)點構成了極大獨立集，證明如下。

命題1：LMCDS算法生成的所有黑色節(jié)點構成極大獨立集。

證明：由染色規(guī)則易知，若黑色節(jié)點處于網內同一層，則它們必不相鄰；若黑色節(jié)點處于網內的不同層，則它們至少相隔兩跳的距離，故黑色節(jié)點構成獨立集。又因為染色完成之后，所有的灰色節(jié)點均被黑色節(jié)點覆蓋，即所有的灰色節(jié)點至少和一個黑色節(jié)點相鄰，若任選一個灰色節(jié)點染黑，所有的黑色節(jié)點將不再構成獨立集，所以該獨立集為極大獨立集。

2.3 連通極小支配集

極小支配集構建完畢之后，要將其連通以實現極小連通支配集的構建。在LMCDS算法中，所有的支配節(jié)點之間是相互獨立的，所以只能從被支配節(jié)點中選擇若干節(jié)點來實現MDS的連通。而生成樹和MIS的構建完成之后，根據節(jié)點之間的連通及父子關系，只需將支配節(jié)點的父節(jié)點加入極小支配集即可實現極小支配集的連通。極小支配集及其支配節(jié)點的父節(jié)點一起構成了極小連通支配集，證明如下。

以圖2（a）的拓撲為例，圖2（b）～2（g）演示了 MIS的構建過程。圖2（g）中所有的黑色節(jié)點構成了MIS，圖2（h）中所有的黑色節(jié)點構成了CDS。

圖2 LMCDS算法構建CDS的應用舉例

3 LMCDS算法性能分析

假設網內節(jié)點數目為n，在探索階段，每個節(jié)點探索鄰居信息，只需發(fā)送一次VISIT消息，因為每個節(jié)點周圍最多有△個鄰居節(jié)點，因此消息復雜度為O（n）。第一階段構建生成樹的過程中最壞情況下的時間復雜度為O（n），消息復雜度為O（n）。構造MIS過程和連通MCDS過程的時間復雜度和消息復雜度都是線性的，所以最壞情況下LMCDS算法的時間復雜度為O（n），消息復雜度為O（n）。

設M為一個拓撲的最小連通支配集，S為該網任意一個連通支配集，并假設網內所有的黑色節(jié)點集合為S1，黑色節(jié)點父節(jié)點集合為S2，所以LMCDS算法中構建的連通支配集S的節(jié)點數目為｜S｜＝｜S1｜＋｜S2｜。由于幾個黑色節(jié)點可能有共同的父節(jié)點，且根節(jié)點無父節(jié)點，所以有｜S2｜≤｜S1｜－1，根據最大獨立集的性質［10］，｜S1｜≤4｜M｜＋1，故｜S｜≤2｜S1｜－1≤8｜M｜＋1。即LMCDS構建的極小連通支配集的數目最多為8｜M｜＋1。

LMCDS算法和WAN算法的性能比較見表1。

表1 兩種算法的性能比較

4 結語

本文基于WAN算法提出了一種分布式極小連通支配集構建方法LMCDS，該算法不但可以生成規(guī)模較小的連通支配集，而且與WAN算法相比，本算法具有較小的消息復雜度，因此在動態(tài)性高、開銷要求小的實時數據傳輸方面具有一定應用價值。

［1］I.Cidon，O.Mokryn.Propagation and leader election in multihop broadcast environment［C］／／Proc.of 12th International Symposium on DIStributed Computing（DISC98），Greece，1998，9：104－119.

［2］Stojmenovic I，Seddigh M，Zunic J.Dominating Sets and Neighbor Elimination Based Broadcasting Algorithms in Wireless Networks［C］／／Proc.of IEEE International Conf.on System Sciences.New Tersey：IEEE Press，2002：14－25.

［3］R.Sivakumar，B.Das，V.Bharghavan.An improved spinebased infrastructure for routing in ad hoc networks［C］／／Proc.of IEEE Symposium on Computers and Communications'98，Athens，Greece，1998.

［4］Wang Yuming，Zhao Dasheng.Construction and analysis of connected dominting set based on serial maximum independent set［J］.J.Huazhong Univ.of Sci.＆Tech.Natural Science E－dition，2011，39（3）：66－70.

［5］B.N.Clark，C.J.Colbourn，D.S.Johnson.Unit disk graphs［J］.Discrete Mathmatics，1990，86：165－177.

［6］Bharghavan V，Das B.Routing in Ad Hoc Networks Using Minimum Connected Dominating Sets［C］／／Proceedings of International Conference on Communications.Montreal，Canada，1997：376－380.

［7］PENG Wei，LU Xichen.A Novel Distribute Approximation Algorithm for Minimum Dominating Set［J］.CHINESE J.COMPUTER，2001，24（3）：254－258.

［8］D.－Z.Du，M.T.Thai，Y.Li，et al.Strongly Connected Dominating Sets in Wireless Sensor Networks with Unidirectional Links［C］／／Proc.APWEB06，2006：13－24.

［9］唐勇，周明天.基于極大獨立集的最小連通支配集的分布式算法［J］.電子學報，2007，37（5）：868－874.TANG Yong，ZHOU Mingtian.Maximal Independent Set Based Distributed Algorithm for Minimum Connected Dominating Set［J］.ACTA ELECTRONICA SINICA，2007，37（5）：868－874.

［10］PENG－JUN WAN.Distributed Construction of Connected Dominating Set in Wireless Ad Hoc Networks［C］／／Proc.of INFOCOM02，2002：1597－1604.