自組織網絡分布式最小連通支配集創建算法

摘 要：針對無線自組織分組（Ad hoc）網絡中最小連通支配集（MCDS）創建NP難問題，提出了一種分布式的最小連通集創建算法DMCA。DMCA基于最大獨立集（MIS）的構建，只需要周圍一跳鄰居的信息，在不超過三跳距離的一對支配節點之間找出一條最短路徑。對DMCA算法的性能分析表明，DMCA具有常數的近似比、線性的時間和消息復雜度。詳細的仿真實驗以及與其他創建最小連通支配集算法的比較表明，提出的DMCA算法在節點數量與節點傳輸范圍變化時創建的最小連通集更小。

關鍵詞：分布式算法； 最小連通支配集； 自組織網絡

中圖分類號： TN915.04文獻標志碼：A

文章編號：1001-3695(2009)06-2241-03

doi:10.3969/j.issn.1001-3695.2009.06.073

Distributed MCDS constructing algorithm in Ad hoc networks

WANG Ling-yan1， ZHANG Qi2， LIU Ai-min1

(1. Dept. of Computer， Chenzhou Vocational Technical College， Chenzhou Hunan 423000， China; 2. School of Computer， Zhejiang University， Hangzhou 310018， China)

Abstract:

For the NP-hard problem of constructing minimum connected dominating set (MCDS) in Ad hoc networks， this paper proposed a novel distributed MCDS constructing algorithm called DMCA. DMCA constructed a MCDS for Ad hoc networks based on a maximal independent set (MIS). In DMCA， each node only required the knowledge of its one-hop neighbors and there existed only one shortest path connecting two dominators these were at most three hops away. The theoretical analysis shows that DMCA was fully localized， had a constant approximation ratio， and O(n) time complexity and O(n) message complexity. Detailed simulation results and comparisons with existed algorithms show that the proposed DMCA algorithm has less size of MCDS with varying node number and transmission range.

Key words：distributed algorithm; minimum connected dominating set; Ad hoc networks

為了提高Ad hoc網絡的性能，近年來一些研究者通過建立虛擬骨干網的方式來實現^{[1， 2]}，該骨干網由屬于連通支配集（connected dominating set， CDS）中的節點構成。通過創建虛擬骨干網，可以把路由節點的數目減小到此虛擬骨干網中的節點。在Ad hoc網絡中，虛擬骨干網在廣播和連通性管理方面發揮著重要的作用。為了減少通信開銷、減少能量消耗，同時延長網絡生存時間和簡化網絡的兩通性管理，往往希望找到一個具有最少節點數目的CDS。但是如何尋找最小連通支配集問題是一個NP問題^{[3， 4]}。在文獻[5]中，提出了一種分布式的MCDS近似構建算法，該算法由三個階段組成，但是該算法的缺陷在于有較高的消息復雜度。Wu等人^[6]提出了另一個分布式算法RBR來為Ad hoc網絡選擇近似MCDS，該算法先找到一個CDS，然后從CDS中去掉多余的節點。盡管該算法簡單，但是生成的MCDS尺寸較大。在文獻[7]中，提出了一種分布式算法GS來構建近似MCDS，該算法先創建一個MIS，然后在所有的被支配節點（dominatee）中找出一些連接節點來連通支配節點。該算法的問題在于同一對支配節點之間會產生多條路徑，從而導致了算法生成的MCDS尺寸較大。

本文針對Ad hoc網絡MCDS創建NP完全問題，提出了一種新的基于分布式機制的最小連通集構建算法DMAC。該算法基于最大獨立集（MIS）的構建，與理論值具有常數的近似比，且有線性的時間和消息復雜度。算法找到惟一的一條最短路徑來連接一對相距三跳距離內的一對支配節點；同時該算法具有完全的局部性，每個節點只需要知道周圍一跳鄰居的信息。位于這條最短路徑上的節點稱為連接（connector）節點。所有支配節點和連接節點構成MCDS。

1 分布式MCDS構建算法

1.1 問題描述

分布式MCDS構建算法DMAC由兩個階段組成：第一個階段是建立一個MIS，其中MIS中的節點稱為支配（dominator）節點；第二個階段是在每對相距不超過三跳距離的支配節點之間選出一條惟一的最短路徑。

假定每個節點都有惟一的節點ID且知道其所有一跳鄰居節點的ID。鄰居節點的ID可以通過每個鄰居節點發送的消息中獲得。無線Ad hoc網絡由n個無線節點組成的集合V構成，這n個無線節點隨機分布于二維空間且具有相同的傳輸范圍。每個無線節點都有一個全向天線。

定義1 集合 V的一個子集 S是一個支配集DS需要滿足以下條件： V中的每個節點 u不是屬于 S就是與 S中的某個節點 v相鄰。 S中的節點稱為支配節點，而不屬于 S的節點稱為被支配節點。

定義2 連通支配集CDS。當 C是一個支配集，并且 C本身構成一個連通圖，則稱 C為連通支配集CDS。

在連通支配集 C中的節點可以利用 V-C中的節點彼此通信。具有最少數目的支配集稱為最小支配集，用MDS表示。而具有最少節點數目且連通的支配集稱為最小連通支配集，用MCDS表示。

定義3 圖 G的節點集 V的一個子集 V′是一個獨立集的條件， V′中的任何兩個節點之間均不存在公共邊。

MIS是節點集 V中具有最多節點數目的獨立集 V′。

1.2 建立最大獨立集

在這個階段，網絡中的每個節點處于以下四個狀態之一，即候選節點（candidate）、支配節點（dominator）、被支配節點（dominatee）和連接節點（connector）。每個節點的初始狀態為候選節點，隨后進入支配節點狀態、被支配節點狀態。而連接節點狀態則只能從被支配節點狀態轉變而來。圖1所示為算法的狀態轉移圖。每個節點中有一個變量 nLower記錄了該節點的一跳鄰居中ID值小于此節點的節點個數，此變量初始化為具有較小ID的一跳鄰居節點的個數。

如果一個候選節點的 nLower為0，則把自己的狀態改為支配節點，然后廣播一個DOMINATOR消息。

當一個候選節點收到DOMINATOR消息時，把自己的狀態改為被支配節點，然后廣播一個DOMINATEE消息。

當一個候選節點收到一個DOMINATEE消息時，如果發出此消息的節點ID小于自己的節點ID，則將自己的 nLower減1，如果此時 nLower的值為0，則把自己的狀態改為支配節點，然后廣播DOMINATOR消息。

算法1 創建MIS

if node.nLower == 0 then

node.status = dominator

broadcastMessage(DOMINATOR)

endif

if received DOMINATOR then

node.status = dominatee

broadcastMessage(DOMINATEE)

endif

if received DOMINATEE then

if(node.nLower -- == 0) then

node.status = dominator

broadcastMessage(DOMINATOR)

endif

endif

1.3 創建最小連通支配集

在這個階段，每個支配節點廣播一個REQUEST_DOMI消息來尋找三跳距離內的其他支配節點。在此消息到達另一個支配節點之前最多被廣播三次。當一個被支配節點第一次收到從另一個支配節點產生的REQUEST_DOMI消息時，該被支配節點把自己的節點ID添加到這個消息中的節點列表，然后廣播這個消息。以這種方式，當一個REQUEST_DOMI消息到達一個支配節點時，這些節點ID構成了從發出此消息的支配節點到接收到這個消息的支配節點的一條最短路徑。當一個支配節點第一次從另一個支配節點收到一個REQUEST_DOMI消息時，則產生一個REPLY_DOMI消息。在這個消息中包含有該消息所經過的節點路徑，然后向該路徑中的下一個節點發送這個REQUEST_DOMI消息。在REQUEST_DOMI中包含的路徑消息是從收到的REQUEST_DOMI消息中包含的節點列表復制而來，但是順序是相反的。當一個節點ID位于REQUEST_DOMI消息所包含的路徑中的被支配節點收到這個REQUEST_DOMI消息時，改變自己的狀態為支配節點，然后將此消息轉發到路徑中指出的下一跳節點。如果兩個位于三跳距離之內的支配節點同時發出REQUEST_DOMI消息，則只有具有較小節點ID的支配節點在收到對方發來的REQUEST_DOMI消息后發出相應的REPLY_DOMI消息來選擇連接節點，并在這兩個節點之間創建最短路徑。由此可以避免在三跳距離之內的支配節點之間創建多條路徑。

算法2 創建MCDS

if node is dominator then

broadcastMessage(REQUEST_DOMI)

if received REQUEST_DOMI then

receiveRequest(REQUEST_DOMI)

endif

 if received REPLY_DOMI then

receiveRepl(REPLY_DOMI)

endif

endif

1.4 算法分析

引理1 本文提出的MCDS算法，對于每個被支配節點 v，在單位圓圖（unit-disk graph）模型中， v最多能連接到5個支配節點。

證明 通過反證法來證明此引理。 S代表位于節點 v的一跳鄰居范圍內的支配節點集。 si（ i∈[1，6]）代表每個與v相鄰的支配節點。假定 |S|≥6，在以 v為中心的單位圓中，如果兩個鄰居支配節點 sj和 sk彼此之間有邊存在，那么 ∠sjvsk的角度最大為60°， sj和 sk的距離最多為一單元。也就是說如果任意兩個支配節點鄰居之間都不存在邊，那么這兩個節點和點v構成的三角形一定大于600，所以 |S|不可能大于5，與假設相矛盾。

對于每個支配節點或被支配節點而言，在 k單元距離之內至多有常數個支配節點。

引理2 對于每個節點 v，在以 v為中心，以 k單元為半徑的圓內部，至多有常數 lk個支配節點^[8]。

基于提出的算法創建MCDS圖之后，加入連接被支配節點到相應的支配節點的邊則覆蓋了網絡中的所有節點。圖2以這種方式顯示了一個MCDS圖的例子。在圖2中，形成了MCDS圖，方形節點代表支配節點或連接節點，而圓形節點代表被支配節點。



引理3 G代表一個單位圓圖， D代表G的一個最小支配集，而 D代表G的任何一個最大獨立集，則有|D|≤5|D|。

證明 既然 D是一個獨立集，由引理1可知，在 D中沒有一個節點能支配超過5個 D中的節點，因此 |D|≥|D|/5。引理得證。

定理1 提出的分布式MCDS創建算法DMCA創建的MCDS與最小CDS具有常數近似因子。

證明 從引理1~3可以直接得到此定理。

定理2 提出的分布式MCDS創建算法DMCA具有 O(n)的時間復雜度和 O(n)的消息復雜度。

證明 對于時間復雜度，提出的算法DMCA由創建MIS和連通MIS為MCDS的過程構成。在創建MIS時，最壞的時間復雜度發生在當所有的節點都是以節點ID遞增排列或遞減排列時，此時在所有節點中最大的節點度為2。在此情況下，每個節點都必須等所有具有較小ID的節點確定它們的狀態之后才能確定自己的狀態。節點n必須等待最長時間n-1才能確定自己的狀態，因此具有O(n)的時間復雜度。在連通MIS為一個MCDS時，由于兩個最近的支配節點之間的距離在三跳內，每個支配節點等待至多5個單位時間來決定是否為連接節點，該算法的第二個階段具有常數的時間復雜度。算法的整個時間復雜度由算法的第一個階段的時間復雜度決定，即O（n）的時間復雜度。

對于通信復雜度，一個支配節點將發送三種消息，包括兩種廣播消息和一種單播消息。支配節點廣播DOMINATOR消息一次，至多廣播REQUEST_DOMI消息一次。除此之外，向所有距離兩跳遠的支配節點和三跳遠的支配節點發送REPLY_DOMI消息。從引理2可知，所有兩跳和三跳遠的支配節點的數目之和為一個常數。因此一個支配節點最多發送常數個REPLY_DOMI消息。對被支配節點而言，也發送三種消息：包括兩種至多廣播三跳的廣播消息和一種單播消息。由引理2可知這些消息之和也為一常數。至于單播消息REPLY_DOMI，由于它是由被支配節點一跳或兩跳遠的支配節點發出的，這種單播消息的數量和也為常數。因此整個算法的消息復雜度也是 O(n)。定理得證。

2 仿真結果

2.1 仿真環境

在仿真環境中， v代表網絡中節點數目， γ代表MCDS中節點的數目， r表示節點移動的傳輸半徑。通過隨機方式在1000×1000平方單元的二維空間產生一定數目的節點來形成仿真的網絡拓撲環境。對于每個節點其位置記錄為（x， y），其中x和y的坐標值隨機且均勻分布于0~1000。如果兩個節點之間的幾何距離小于無線傳輸半徑，則在這兩個節點之間有一條邊存在；如果生成的圖是非連通的，則用同樣的參數重新生成一個圖。

2.2 仿真結果比較

為了對提出的DMCA算法的有效性進行驗證，將提出的算法與RBR算法^[6]、GS算法^[7]進行比較。

場景一 節點傳輸范圍的變化對算法性能的影響。節點數目分別為200和400時，對于每個 v，節點的傳輸半徑從100變化到1 000。

圖3和4所示為三種算法的MCDS大小隨節點傳輸半徑從100增加到1 000時的性能。從圖中可以看出，提出的DMCA算法性能明顯優于其他兩種算法。尤其是在較小的和中等大小的傳輸半徑時（小于700時）更加顯著。

當傳輸半徑為200時，提出的DCMA算法生成的MCDS大小為0.25，而RBR與GS算法生成的MCDS大小分別為0.63與0.3，是提出的算法的2.52和1.2倍。平均來看，RBR算法生成MCDS的大小是提出的DMCA算法大小的3.1倍。當傳輸半徑為300時，提出的DMCA算法生成的MCDS大小與RBR算法生成的MCDS大小達到了最大的差，提出的算法的MCDS大小為0.15，而后者算法的大小為0.6，兩者為4倍關系。與GS算法相比，提出的DMCA算法的性能也更優，從平均值而言，兩者的比率為1.2。當節點數目為400時，此時RBR與GS算法所創建的MCDS的尺寸都有所增加，而提出的DMCA算法的大小基本保持不變，因此，三種算法的差值進一步增加。這也證明了提出的DMCA算法具有很好的適應性。其原因在于，DMCA算法創建的MCDS與最小CDS具有常數近似因子，不受網絡規模的影響。另外，三種算法的MCDS大小都隨著傳輸半徑的增加而減小，原因是大的傳輸半徑導致了連接豐富的稠密網絡，在一個節點的覆蓋范圍內產生了大量的鄰居節點，因此減小了MCDS的尺寸。



場景二 節點數目變化對算法性能的影響。節點傳輸半徑分別為200和400時，而節點的數量從100變化到1 000。

圖5和6所示為三種算法的MCDS尺寸隨著節點數目變化時的性能。從圖中也可以清晰地看出提出的DMCA算法的性能明顯優于其他兩種算法。



當傳輸半徑固定為200時，從圖5中可以看出，與GS算法相比，DMCA算法生成的MCDS尺寸也更小。提出的DMCA算法的MCDS尺寸隨著節點數量的增加而逐漸減小，其值從0.4減小到0.07；而RBR算法的MCDS尺寸始終大于0.63，且隨著節點數量的增加而有微小的增加。當節點數量為1 000時，兩種算法的差值達到最大，其MCDS尺寸大小相差11倍。平均而言，RBR算法所創建的MCDS尺寸是提出的DMCA算法的4.4倍。

當傳輸半徑固定為400時，此時節點數為300時，提出的DMCA算法與GS算法之間的性能差最大。提出的DMCA算法生長的MCDS的尺寸為0.14，而GS算法生成的MCDS的尺寸為0.18，是前者的1.3倍。從平均值而言，其比率為1.1。同時可以看出，當半徑分別為200和400時，其性能結果基本相似。另外，隨著節點數目的增加，提出的DMCA算法與GS算法生成的MCDS尺寸均會減小。這意味著這兩種算法具有更好的性能。而RBR算法并沒有這種特性；相反，在RBR算法中，MCDS尺寸隨著節點數量的增多保持不便或緩慢地增加。其原因在于提出的DMCA算法，只需要根據其一跳鄰居節點的信息就能在不超過三跳距離的一對支配節點之間找出一條惟一的最短路徑，受節點密度與數量的影響非常小。

3 仿真結果

為了解決最小連通支配集創建NP難問題，本文提出了一種新的分布式最小連通集構建算法DMCA。DMCA構建算法由兩個階段組成：第一個階段是建立一個最大獨立集（MIS），其中MIS中的節點成為支配節點；第二個階段是在每對相距不超過三跳距離的支配節點之間選出一條惟一的最短路徑。理論分析證明了該算法與理論值具有常數的近似比，且有線性的時間和消息復雜度。實驗結果及與其他算法的比較證明了該算法在節點數量、傳輸半徑變化的場景下均表現出了較好的性能。由于該算法只需要根據其一跳鄰居節點的信息就能在不超過三跳距離的一對支配節點之間找出一條惟一的最短路徑，受節點密度與數量的影響非常小，適合于拓撲結構稠密的大型無線Ad hoc網絡。



參考文獻：

[1]SUNIL K， VINEET S R， JING D. Medium access control protocols for Ad hoc wireless networks: a survey [J]. Ad hoc Networks， 2006， 4(5): 326-358.

［2］CARDEI M， DU Ding-zhu. Improving wireless sensor network lifetime through power aware organization [J]. ACM Wireless Networks， 2005， 11(3): 213-229.

［3］GAREYAND D， JOHNSON D S. Computers and intractability: a guide to the theory of NP-completeness [M]. New York:Freeman Co， 1979.

［4］BHARGHAVAN V， DAS B. Routing in Ad hoc networks using minimum connected dominating set[C]//Proc of International Conference on Communications. Piscataway:IEEE Press， 1997:145-160.

［5］STOJMENOVIC I， SEDDIGH S， ZUNIC J. Dominating sets and neighbor elimination based broadcasting algorithms in wireless networks [J]. IEEE Trans on Parallel and Distributed Systems， 2002， 13(1): 14-25.

［6］WU Jie， LOU Wei. On reducing broadcast redundancy in Ad hoc wireless networks[C]//Proc of the 36th Annual Hawaii International Conference on System Sciences. Piscataway:IEEE Press， 2003:305-314.

［7］ALZOUBI K， LI Xiang-yang， WANG Yu， et al. Geometric spanners for wireless Ad hoc network [J]. IEEE Trans on Parallel and Distributed Systems， 2003， 14(4): 408-421.

［8］MARATHE M V， BREU H， RAVI H S. Simple heuristics for unit disk graph [J]. Networks， 1995， 25(1): 59-68.