無線傳感器網(wǎng)絡(luò)極小連通支配集算法的改進(jìn)*

張 靜，賈春福，楊 挺

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

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

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

1 算法

1.1 定義

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

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

1.2 數(shù)學(xué)模型

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

對于支配集需要滿足:任何V－D節(jié)點至少要與一個集合D內(nèi)節(jié)點相連。用以下數(shù)學(xué)模型描述支配集:

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

圖1 支配集不連通示例

綜上所述，極小連通支配集的數(shù)學(xué)模型表示如下:

目標(biāo):

約束:

1.3 WL［11］算法回顧

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

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

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

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

上述標(biāo)記過程求出連通支配集，接下來通過優(yōu)化規(guī)則減少CDS的大小。在網(wǎng)絡(luò)中，給每個節(jié)點分配唯一標(biāo)識的 id，N［v］是節(jié)點 v的鄰節(jié)點閉集合，N［v］=v∪N(v)。

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

當(dāng)N［v］=N［u］時，節(jié)點v或u都可以標(biāo)記為非支配點，為了保證僅有一個節(jié)點變?yōu)榉侵潼c，選擇節(jié)點id較小的那個節(jié)點標(biāo)記為非支配點。

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

1.4 IWL 算法描述

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

基于上述分析，我們可以對上述WL算法進(jìn)行改進(jìn)，提出IWL算法。該算法中標(biāo)記過程可以省略，直接對圖G應(yīng)用改進(jìn)的優(yōu)化規(guī)則，一次完成而不需分階段執(zhí)行，這樣就消除了由于分步實施算法具有的不完整性。初始時標(biāo)記網(wǎng)絡(luò)中所有節(jié)點都為支配點，算法描述如下:

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

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

算法的執(zhí)行步驟如下:

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

(2)接收到鄰居節(jié)點發(fā)送的N(v)消息后，開始運行Rule 1a，如果滿足Rule 1a則變?yōu)榉侵潼c，否則保持支配點不變。并將節(jié)點的最新狀態(tài)信息廣播給周圍鄰居節(jié)點。

(3)當(dāng)節(jié)點接收到所有鄰居節(jié)點發(fā)送的最新狀態(tài)信息后，開始運行Rule 2a，如果滿足Rule 2a則變?yōu)榉侵潼c，否則保持支配點不變。

(4)算法結(jié)束。

定理1 運行IWL算法后形成的支配點集是該網(wǎng)絡(luò)的連通支配集。

證明:算法假定初始所有節(jié)點都是支配點，Rule 1a是指當(dāng)支配點v所支配的節(jié)點也同時被支配點u支配的話，那么節(jié)點v可以變?yōu)榉侵潼c，這樣可以使得節(jié)點v周圍的所有節(jié)點還能被節(jié)點u所支配，同時與節(jié)點v相連的支配點可以與支配點u連通。Rule 2a是指當(dāng)且僅當(dāng)支配點v的所有鄰居節(jié)點能被支配點u或w同時支配的話，那么節(jié)點v可以變?yōu)榉侵潼c，這樣可以使得節(jié)點v周圍的所有的非支配節(jié)點還能被支配，同時與節(jié)點v相連的支配點可以與支配點u或w相連，因此運行完該算法之后剩余的支配點集是該網(wǎng)絡(luò)的連通支配集。

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

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

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

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

1.5 IWL算法圖例說明

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

為了說明算法有效性，通過圖例說明IWL算法的執(zhí)行過程。給定圖2(a)所示，初始時節(jié)點都是支配點。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)，節(jié)點2，3，4，5 都變?yōu)榉侵潼c。

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

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

2 仿真及結(jié)果分析

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

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

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

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

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

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

圖4 節(jié)點數(shù)目固定性能比較

3 結(jié)論

本文根據(jù)WL算法，提出的一種簡單有效的分布式算法IWL，解決了WL算法分步實施的缺點，使得求解連通支配集的算法得到簡化。算法只要求網(wǎng)絡(luò)節(jié)點具有局部的網(wǎng)絡(luò)拓?fù)湫畔ⅲ朔思惺剿惴ㄐ枰鸭麄€網(wǎng)絡(luò)拓?fù)湫畔⒌娜秉c，因而算法的可伸縮性好。仿真結(jié)果表明，算法能有效地得到較小的網(wǎng)絡(luò)連通支配集，其性能優(yōu)于被比較的分布式算法。此算法可以在網(wǎng)絡(luò)中自動形成一個虛擬骨干網(wǎng)，從而可為網(wǎng)絡(luò)中的廣播和路由操作提供一個有效的通信基礎(chǔ)。

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

［2］ 孫雨耕，張靜.無線自組傳感器網(wǎng)絡(luò)［J］.傳感技術(shù)學(xué)報，2004，17(2):331－335，348.

［3］ 馬祖長，孫怡寧，梅濤.無線傳感器網(wǎng)絡(luò)綜述［J］.通信學(xué)報，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的高效節(jié)能協(xié)議［J］.傳感技術(shù)學(xué)報，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］.計算機學(xué)報，2001，24(3):254－258.

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

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

［15］張靜，賈春福.基于自適應(yīng)拓?fù)渥兓臒o線傳感器網(wǎng)絡(luò)路由協(xié)議［J］.天津大學(xué)學(xué)報，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.