無線傳感器網絡極小連通支配集算法的改進*

張 靜，賈春福，楊 挺

(1.天津工業大學工程教學實習訓練中心，天津300387;2.南開大學信息技術科學學院，天津300071;3.天津大學電氣與自動化工程學院，天津300072)

集成了傳感器、微機電系統和網絡三大技術而形成的傳感器網絡是一種全新的信息獲取和處理技術［1－3］。在無線傳感器網絡中，除了少數節點需要移動以外，大部分節點都是靜止的。它要求設計的算法必須具有快速收斂的特性，減少路由查找的開銷，提高路由發現的性能和效率。基于最小連通支配集的路由方法是一個很好的分層路由［4－7］方法，它將路由過程簡化到生成的較小的子網中。這意味著在先應式路由中只有網關節點需要維持路由信息，而在反應式路由中研究空間被簡化到這個MCDS中。MCDS中的網關節點構成了高一級的虛擬骨干網，而每個網關節點在自己的簇中都起著控制中心的作用，用于路由分組和廣播路由信息。明顯地，這種方法的有效性很大程度上依賴于發現和維持一個MCDS及與之相應的子網的大小。不幸的是，對大部分圖來說，求一個MCDS的問題屬NP－C問題［8］，在實際應用中需要設計近似求解算法。目前已有的算法主要分兩類，集中式算法［9－10］和分布式算法［11－17］。集中式算法要求每個節點具有整個網絡的拓撲結構信息，因而不適合移動網絡多變的特點，可伸縮性差。分布式算法的主要思想是通過節點之間的局部交互操作在網絡中迅速構造一個虛擬骨干網。

有關連通支配集的算法，國內外已經有許多人從事這一方向的研究。其中WL［11，17］提出了求解連通支配集的簡單且有效的方法，隨后又提出多種改進算法［12－16］。WL算法求解連通支配集分為標記階段和優化階段，由于分步實施算法具有不完整性，即缺乏措施將兩個連續的階段銜接起來，所以使單個節點無法判斷下一個階段何時開始，因此具有不完整性。本文首先提出連通支配集的數學模型，基于WL算法進行優化改進，提出IWL算法并通過仿真說明算法的有效性。

1 算法

1.1 定義

用一個連通的簡單無向圖G=(V，E)來表示無線自組傳感器網絡，其中:V是一組節點的集合，每個節點表示一個傳感器;E是一組邊的集合，每條邊e=(u，v)∈E(其中 u，v∈V)表示節點 u 和節點 v彼此都在對方的無線發射范圍內。節點u的相鄰節點集記為N(u)。節點u的相鄰節點閉集記為N［u］。

定義1 一個圖G的某個節點子集D是支配集(DS)是指G中所有在V－D中的節點都至少和D中的一個節點相鄰。圖G的支配集D稱為連通支配集(CDS)是指由 D誘導的子圖 G［D］是連通圖。CDS中的節點稱為支配節點，也稱為網關節點;不在該集中的節點則被稱為非支配節點或非網關節點。如果圖G中沒有比D更小的連通支配集，則D稱為最小連通支配集(MCDS)。

1.2 數學模型

我們先描述出該圖的支配集的數學模型，然后選出部分節點作為支配節點，保證支配集連通，得到的就是連通支配集的數學模型。

對于支配集需要滿足:任何V－D節點至少要與一個集合D內節點相連。用以下數學模型描述支配集:

對于支配集內支配點有兩種可能不連通。如圖1(a)和1(b)所示。

圖1 支配集不連通示例

綜上所述，極小連通支配集的數學模型表示如下:

目標:

約束:

1.3 WL［11］算法回顧

標記過程:給定一個連通的簡單無向圖 G=(V，E)，M(v)標記節點v是否為支配點，M(v)=T為支配點，F為非支配點。假定初始時每個節點都是非支配點，N(v)={v|{v，u}∈E}表示節點v的鄰節點開集合。

(1)初始每個節點M(v)=F;

(2)每個節點v向它的鄰居節點廣播它所有的鄰節點開集合N(v);

(3)當節點接收到所有鄰節點的信息后，如果存在兩個不相鄰的節點，則宣布自己為支配點，即M(v)=T。

上述標記過程求出連通支配集，接下來通過優化規則減少CDS的大小。在網絡中，給每個節點分配唯一標識的 id，N［v］是節點 v的鄰節點閉集合，N［v］=v∪N(v)。

Rule 1:在支配集內兩個相鄰節點u和v，如果N［v］?N［u］，并且 id(v)＜id(u)，則將 v標記為非支配點。

當N［v］=N［u］時，節點v或u都可以標記為非支配點，為了保證僅有一個節點變為非支配點，選擇節點id較小的那個節點標記為非支配點。

Rule 2:假定在支配集內節點v和w與節點u相鄰，如果 N(v)?N(u)∪N(w)，并且 id(v)=min{id(v)，id(u)，id(w)}，則將 v標記為非支配點。

1.4 IWL 算法描述

在WL算法的標記過程中，只有當節點v的所有鄰居節點都是相互連通的，也就是導出的子圖是完全連通圖時，節點v才會標記為非支配點。在無線傳感器網絡中，節點被隨機拋撒在一定區域，大部分節點都會有兩個鄰居節點是不相鄰的，只有極少數節點的所有鄰居節點是相互連通。所以WL算法的標記過程只能使得極小部分節點變為非支配點，主要是通過優化規則再精簡連通支配集的大小。但是我們可以看到，在 Rule 1，如果節點 v和 u滿足 N［v］?N［u］，但是 id(v)＞id(u)，那么節點 v不會被標記為非支配點。同樣在Rule 2中，如果節點u，v，w 滿足 N(v)?N(u)∪N(w)，但是 id(v)不是最小的話，節點v也不會被標記為非支配點。在WL算法中節點id的引入主要是避免當N［v］=N［u］時，節點u，v同時變為非支配點。

基于上述分析，我們可以對上述WL算法進行改進，提出IWL算法。該算法中標記過程可以省略，直接對圖G應用改進的優化規則，一次完成而不需分階段執行，這樣就消除了由于分步實施算法具有的不完整性。初始時標記網絡中所有節點都為支配點，算法描述如下:

Rule 1a:假定u，v都是支配點，節點v滿足下列任意條件可以標記為非支配點:

Rule 2a:假定支配點u和w是支配點v的鄰居節點，節點v滿足下列任意條件可以標記為非支配點:

算法的執行步驟如下:

(1)假設初始所有節點為支配節點，所有節點首先發送hello消息給周圍鄰居節點，收集到鄰居節點信息后形成N(v)，并將N(v)廣播給鄰居節點。

(2)接收到鄰居節點發送的N(v)消息后，開始運行Rule 1a，如果滿足Rule 1a則變為非支配點，否則保持支配點不變。并將節點的最新狀態信息廣播給周圍鄰居節點。

(3)當節點接收到所有鄰居節點發送的最新狀態信息后，開始運行Rule 2a，如果滿足Rule 2a則變為非支配點，否則保持支配點不變。

(4)算法結束。

定理1 運行IWL算法后形成的支配點集是該網絡的連通支配集。

證明:算法假定初始所有節點都是支配點，Rule 1a是指當支配點v所支配的節點也同時被支配點u支配的話，那么節點v可以變為非支配點，這樣可以使得節點v周圍的所有節點還能被節點u所支配，同時與節點v相連的支配點可以與支配點u連通。Rule 2a是指當且僅當支配點v的所有鄰居節點能被支配點u或w同時支配的話，那么節點v可以變為非支配點，這樣可以使得節點v周圍的所有的非支配節點還能被支配，同時與節點v相連的支配點可以與支配點u或w相連，因此運行完該算法之后剩余的支配點集是該網絡的連通支配集。

定理2 IWL分簇算法中，整個網絡的廣播消息量復雜度為O(n)。

證明:算法初始所有節點發送信息，消息量為n;任意節點v將N(v)廣播給鄰居節點，消息量為n;節點宣布為非支配點發送消息m個，其中m為非支配點的個數。IWL分簇算法整個廣播消息量為(2n+m)，所以，整個網絡的廣播消息量復雜度為O(n)。

定理3 IWL分簇算法中，整個網絡的時間復雜度為 O(Δ2+nlgΔ)。

證明:IWL分簇算法中，網絡的時間復雜度就是單個節點最壞情況下的時間復雜度之和，每一個節點都要與周圍鄰居節點比較，Δ為節點的最大度，單個節點比較花費O(lgΔ)。所有節點同時運行規則Rule 1a，花費O(Δ2)，剩余支配點運行規則Rule 2a，算法最壞情況是所有節點運行規則Rule 1a后都保持支配點，n個節點運行規則 Rule 2a，所以給出IWL分簇算法整個網絡的時間復雜度為 O(Δ2+nlgΔ)。

1.5 IWL算法圖例說明

圖2 算法中Rule 1a和Rule 2a的圖示說明

為了說明算法有效性，通過圖例說明IWL算法的執行過程。給定圖2(a)所示，初始時節點都是支配點。N(1)={2，3，4，5}，N(2)={1，4，5}，N(3)={1}，N(4)={1，2}，N(5)={1，2}.N［2］?N［1］，N［3］?N［1］，N［4］?N［1］，N［5］?N［1］，通過Rule 1a(2)，節點2，3，4，5 都變為非支配點。

為了說明IWL算法較WL算法的優越性，我們也通過圖例進行說明分析。給定圖2(a)所示支配集，不難看出N［2］?N［1］，但是 id(2)＞id(1)，則不滿足 WL的優化規則Rule 1，所以節點2不能標記為非支配點。由于N［2］?N［1］，N［1］?N［2］，滿足本文給定的Rule 1a(2)，因此節點2可以標記為非支配點。同樣給定圖2(b)，N(2)?N(1)∪N(3)，但是 id(2)＞id(1)，則不滿足WL的優化規則Rule 2，所以節點2不能標記為非支配點。由于N(2)?N(1)∪N(3)，N(3)?N(1)∪N(2)，但是 N(1)?N(2)∪N(3)，id(2)＜id(3)，滿足本文給定的Rule2a(2)，因此節點2可以標記為非支配點。

類似于參考文獻［14－17］中提出的改進算法，上述規則中節點id可以替換為節點的度數或節點能量級別。當規則中選擇節點度數大的作為支配點，則可以減少支配集的大小;如果選擇能量級別高的節點作為支配點，能夠有效延長每個節點的平均壽命。

2 仿真及結果分析

為了評價算法IWL，我們以實例進行計算機仿真，并與 WL［11］算法和 WMCDS［16］進行比較，評估算法在生成較小連通支配集的性能。

測試所用的拓撲通過如下方法產生:在長度L=100 m，寬度W=100 m的區域內隨機播撒數目為N的節點，假定每個傳感器節點都有相同的通訊半徑R，這樣產生的圖為簡單無向圖。然后設定節點的通訊半徑R，如果兩個節點的距離小于R，在這兩個節點間將有一條連線。通過下面的步驟計算連通支配集:

(1)首先判斷產生的該隨機圖是否連通。如果不是連通圖則重新進行播撒，否則進行下一步。

(2)對隨機圖分別應用IWL算法、WMCDS算法和WL算法，計算產生的支配集所占的比例。

設計了兩類實驗:一類是通訊半徑R固定為40 m時，不斷按步長5個增加節點數從30個到80個;另一類是節點數目固定為40個，不斷按步長為5 m增加通訊半徑由30 m到80 m。對每一個節點/通訊半徑的組合，隨機生成50個拓撲，對于每個拓撲進行實驗，運行本算法。我們得到圖3和圖4的模擬結果。分析實驗曲線可以發現，隨著拓撲節點數(或者單個節點發射距離)的增加，三個算法產生的連通支配集所占的比例都在減少，而IWL算法優于其他兩個算法。在節點間連通性較強的情況下，IWL算法和WMCDS算法以及WL算法均可以得到很好的結果。因此IWL算法性能整體上是優于其他兩個算法的。

圖3 通訊半徑固定性能比較

圖4 節點數目固定性能比較

3 結論

本文根據WL算法，提出的一種簡單有效的分布式算法IWL，解決了WL算法分步實施的缺點，使得求解連通支配集的算法得到簡化。算法只要求網絡節點具有局部的網絡拓撲信息，克服了集中式算法需要搜集整個網絡拓撲信息的缺點，因而算法的可伸縮性好。仿真結果表明，算法能有效地得到較小的網絡連通支配集，其性能優于被比較的分布式算法。此算法可以在網絡中自動形成一個虛擬骨干網，從而可為網絡中的廣播和路由操作提供一個有效的通信基礎。

［1］ 任豐原，黃海寧，林闖.無線傳感器網絡［J］.軟件學報，2003，14(7):1282－1291.

［2］ 孫雨耕，張靜.無線自組傳感器網絡［J］.傳感技術學報，2004，17(2):331－335，348.

［3］ 馬祖長，孫怡寧，梅濤.無線傳感器網絡綜述［J］.通信學報，2004，25(4):114－122.

［4］ Yi S，Heo J，Cho Y，et al.PEACH:Power-Efficient and Adaptive Clustering Hierarchy Protocol for Wireless Sensor Networks［J］.Computer Communications，2007(30):2842－2852.

［5］ 楊偉，劉潤杰，申金媛.一種基于LEACH的高效節能協議［J］.傳感技術學報，2010，23:1153－1157.

［6］ Stanislava S，Henizelman W B.Cluster Head Election Techniques for Coverage Preservation in Wireless Sensor Networks［J］.Ad Hoc Networks，2009，5(7):955－972.

［7］ Muhammad Tariq，Yong Pyo Kim，Jun Hwan Kim，et al.Energy Efficient and Reliable Routing Scheme for Wireless Sensor Networks［C］//2009 International Conference on Communication Software and Networks，2009:181－185.

［8］ Garey M L，Johnson D S.Computers and Intractability;A Guide to the Theory of NP-Comleteness［M］.San Francisico;W H Freeman，1979.

［9］ Chiang C，Wu H，Liu W，et al.Routing in Clustered Multihop Mobilewireless Networks with Fading Channel［C］//IEEE Singapore International Conference on Networks，1997，Singapore，1997:197－211.

［10］ Ravi Prakash.A Routing Algorithm for Wireless Ad Hoc Networks with Unidirectional Links［J］.Wireless Networks，2001，7:617－625.

［11］ Wu Jie，Li Hai-Lan.On Calculating Connected Dominating Set for Efficient Routing in Ad-Hoc Wireless Network［C］//Proc Third International Workshop on Discrete Algorithms and Methods for MobileComputing and Communications(DIAL M’99)，Seattle，1999

［12］彭偉，盧錫成.一個新的分布式最小連通支配集近似算法［J］.計算機學報，2001，24(3):254－258.

［13］張靜，孫雨耕，房朝暉.能量有效的最小連通支配集近似算法［J］.傳感技術學報，2004，17(4):603－606，610.

［14］閻新芳，孫雨耕，胡華東.基于極大權的最小連通支配集啟發式算法［J］.電子學報，2004，32(11):1774－1777.

［15］張靜，賈春福.基于自適應拓撲變化的無線傳感器網絡路由協議［J］.天津大學學報，2007，40(9):1054－1059.

［16］ Zhang Jing，Jia Chun-Fu.Minimum Connected Dominating Set Algorithm with Weight in Wireless Sensor Networks［C］//The 4th International Conference on Wireless Communications，Networking and Mobile Computing.2008.1－4.

［17］ Wu Jie，Gao Ming.Stojmenovic on Calculating Power-Aware Connected Dominating Sets for Efficient Routing in Ad Hoc Wireless Networks［C］//Proceedings of the IEEE International Conference on Parallel.Valencia:IEEE Computer Society Publisher，2001.346－353.