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

狄元博 陶 凱 葉永安

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

1 引言

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

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

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

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

2 LMCDS算法描述

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

圖1 LMCDS算法流程

2.1 生成樹的構建

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

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

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

規則3：同時收到HELLO消息的節點，按時隙轉發HELLO消息，節點度大的節點優先轉發。按時隙轉發保證了每個節點只有唯一的父節點。

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

2.2 極小支配集的構建

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

構建MIS開始之前，首先給出一個鍵值（Key）的概念，對任意節點u，定義其鍵值為 K（u）＝（deg（u），ID（u）），即一個節點的鍵值是其節點度與節點號的有序組合。給定任意兩個節點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。初始時所有節點均為白色，然后按照如下操作逐步對各個節點進行染色，直至所有的節點都被染成黑色或灰色，則停止染色。

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

規則2：若支配層中還存在白色節點就按照規則1繼續染色。

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

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

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

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

2.3 連通極小支配集

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

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

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

3 LMCDS算法性能分析

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

設M為一個拓撲的最小連通支配集，S為該網任意一個連通支配集，并假設網內所有的黑色節點集合為S1，黑色節點父節點集合為S2，所以LMCDS算法中構建的連通支配集S的節點數目為｜S｜＝｜S1｜＋｜S2｜。由于幾個黑色節點可能有共同的父節點，且根節點無父節點，所以有｜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，該算法不但可以生成規模較小的連通支配集，而且與WAN算法相比，本算法具有較小的消息復雜度，因此在動態性高、開銷要求小的實時數據傳輸方面具有一定應用價值。

［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.