狄元博 陶 凱 葉永安

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

1 引言

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

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

近似算法分為集中式構(gòu)建算法和分布式構(gòu)建算法。集中式構(gòu)建算法需要獲得整個(gè)網(wǎng)的拓?fù)浣Y(jié)構(gòu)，這對(duì)成員規(guī)模較大時(shí)是一筆不小的開(kāi)銷。分布式構(gòu)建算法無(wú)線獲得整個(gè)網(wǎng)的拓?fù)浣Y(jié)構(gòu)，具有較好的拓?fù)鋭?dòng)態(tài)適應(yīng)性。

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

2 LMCDS算法描述

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

圖1 LMCDS算法流程

2.1 生成樹的構(gòu)建

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

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

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

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

當(dāng)所有節(jié)點(diǎn)的Level值均不為零時(shí)，生成樹構(gòu)建完成。此時(shí)，所有節(jié)點(diǎn)的Level值和父節(jié)點(diǎn)都已確定。

2.2 極小支配集的構(gòu)建

生成樹構(gòu)建完畢之后，該網(wǎng)隨之分層完畢。接下來(lái)開(kāi)始構(gòu)建該網(wǎng)的極小支配集。根據(jù)圖論的知識(shí)，一個(gè)圖的極大獨(dú)立集（MIS）都是它的極小支配集（MDS），所以可以通過(guò)構(gòu)建MIS的方法實(shí)現(xiàn)MDS的構(gòu)建。

構(gòu)建MIS開(kāi)始之前，首先給出一個(gè)鍵值（Key）的概念，對(duì)任意節(jié)點(diǎn)u，定義其鍵值為 K（u）＝（deg（u），ID（u）），即一個(gè)節(jié)點(diǎn)的鍵值是其節(jié)點(diǎn)度與節(jié)點(diǎn)號(hào)的有序組合。給定任意兩個(gè)節(jié)點(diǎn)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算法采用染色法構(gòu)建MIS。初始時(shí)所有節(jié)點(diǎn)均為白色，然后按照如下操作逐步對(duì)各個(gè)節(jié)點(diǎn)進(jìn)行染色，直至所有的節(jié)點(diǎn)都被染成黑色或灰色，則停止染色。

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

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

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

染色完成之后，所有的黑色節(jié)點(diǎn)構(gòu)成了極大獨(dú)立集，證明如下。

命題1：LMCDS算法生成的所有黑色節(jié)點(diǎn)構(gòu)成極大獨(dú)立集。

證明：由染色規(guī)則易知，若黑色節(jié)點(diǎn)處于網(wǎng)內(nèi)同一層，則它們必不相鄰；若黑色節(jié)點(diǎn)處于網(wǎng)內(nèi)的不同層，則它們至少相隔兩跳的距離，故黑色節(jié)點(diǎn)構(gòu)成獨(dú)立集。又因?yàn)槿旧瓿芍?，所有的灰色?jié)點(diǎn)均被黑色節(jié)點(diǎn)覆蓋，即所有的灰色節(jié)點(diǎn)至少和一個(gè)黑色節(jié)點(diǎn)相鄰，若任選一個(gè)灰色節(jié)點(diǎn)染黑，所有的黑色節(jié)點(diǎn)將不再構(gòu)成獨(dú)立集，所以該獨(dú)立集為極大獨(dú)立集。

2.3 連通極小支配集

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

以圖2（a）的拓?fù)錇槔?，圖2（b）～2（g）演示了 MIS的構(gòu)建過(guò)程。圖2（g）中所有的黑色節(jié)點(diǎn)構(gòu)成了MIS，圖2（h）中所有的黑色節(jié)點(diǎn)構(gòu)成了CDS。

圖2 LMCDS算法構(gòu)建CDS的應(yīng)用舉例

3 LMCDS算法性能分析

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

設(shè)M為一個(gè)拓?fù)涞淖钚∵B通支配集，S為該網(wǎng)任意一個(gè)連通支配集，并假設(shè)網(wǎng)內(nèi)所有的黑色節(jié)點(diǎn)集合為S1，黑色節(jié)點(diǎn)父節(jié)點(diǎn)集合為S2，所以LMCDS算法中構(gòu)建的連通支配集S的節(jié)點(diǎn)數(shù)目為｜S｜＝｜S1｜＋｜S2｜。由于幾個(gè)黑色節(jié)點(diǎn)可能有共同的父節(jié)點(diǎn)，且根節(jié)點(diǎn)無(wú)父節(jié)點(diǎn)，所以有｜S2｜≤｜S1｜－1，根據(jù)最大獨(dú)立集的性質(zhì)［10］，｜S1｜≤4｜M｜＋1，故｜S｜≤2｜S1｜－1≤8｜M｜＋1。即LMCDS構(gòu)建的極小連通支配集的數(shù)目最多為8｜M｜＋1。

LMCDS算法和WAN算法的性能比較見(jiàn)表1。

表1 兩種算法的性能比較

4 結(jié)語(yǔ)

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

［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］唐勇，周明天.基于極大獨(dú)立集的最小連通支配集的分布式算法［J］.電子學(xué)報(bào)，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.