張 靜，賈春福，楊 挺

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

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

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

1 算法

1.1 定義

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

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

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

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

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

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

圖1 支配集不連通示例

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

目標(biāo):

約束:

1.3 WL［11］算法回顧

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

(1)初始每個(gè)節(jié)點(diǎn)M(v)=F;

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

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

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

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

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

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

1.4 IWL 算法描述

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

1.5 IWL算法圖例說明

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

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

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

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

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

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

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

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

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

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

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

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

3 結(jié)論

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

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

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

［3］ 馬祖長(zhǎng)，孫怡寧，梅濤.無線傳感器網(wǎng)絡(luò)綜述［J］.通信學(xué)報(bào)，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］ 楊偉，劉潤(rùn)杰，申金媛.一種基于LEACH的高效節(jié)能協(xié)議［J］.傳感技術(shù)學(xué)報(bào)，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］彭偉，盧錫成.一個(gè)新的分布式最小連通支配集近似算法［J］.計(jì)算機(jī)學(xué)報(bào)，2001，24(3):254－258.

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

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

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