馬晨明,王萬良,洪 榛

(1.浙江工業(yè)大學(xué)信息工程學(xué)院,杭州 310023;2.浙江工業(yè)大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院,杭州 310023;3.浙江理工大學(xué)機(jī)械與自動控制學(xué)院,杭州 310018)

?

異構(gòu)無線傳感器網(wǎng)絡(luò)中基于CDS樹的拓?fù)淇刂品椒?

馬晨明1,王萬良2*,洪 榛3

(1.浙江工業(yè)大學(xué)信息工程學(xué)院,杭州 310023;2.浙江工業(yè)大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院,杭州 310023;3.浙江理工大學(xué)機(jī)械與自動控制學(xué)院,杭州 310018)

拓?fù)淇刂剖菬o線傳感器網(wǎng)絡(luò)中節(jié)約能量、延長網(wǎng)絡(luò)生命的關(guān)鍵技術(shù)。針對現(xiàn)有拓?fù)淇刂品椒ㄖ饕性谕瑯?gòu)網(wǎng)絡(luò)中作為拓?fù)錁?gòu)建或拓?fù)渚S護(hù)單獨(dú)研究的問題,提出了包含兩個過程的異構(gòu)網(wǎng)絡(luò)分布式拓?fù)淇刂扑惴ˋ3M。拓?fù)錁?gòu)建基于最小連通支配集構(gòu)建虛擬骨干樹,在保證連通性的同時關(guān)閉網(wǎng)絡(luò)冗余節(jié)點以降低能耗;拓?fù)渚S護(hù)對網(wǎng)絡(luò)性能進(jìn)行評估,當(dāng)現(xiàn)有網(wǎng)絡(luò)性能嚴(yán)重下降時,改變拓?fù)湟员Ｕ暇W(wǎng)絡(luò)的穩(wěn)定運(yùn)行。理論分析和仿真實驗證實算法能夠以較小的時間和消息代價減少拓?fù)錁?gòu)建能耗并延長網(wǎng)絡(luò)時間。

異構(gòu)無線傳感器網(wǎng)絡(luò);拓?fù)淇刂?A3M算法;拓?fù)錁?gòu)建;拓?fù)渚S護(hù);最小連通支配集

無線傳感器網(wǎng)絡(luò)由傳感器節(jié)點自組織形成[1],節(jié)點能量受限且通常不易補(bǔ)充,因此如何節(jié)省能量成為研究無線傳感器網(wǎng)絡(luò)的重要問題。拓?fù)淇刂芠2]是保證全網(wǎng)連通、平衡節(jié)點能耗,增加運(yùn)行時間的高效可行技術(shù),它包括拓?fù)錁?gòu)建與拓?fù)渚S護(hù)兩個過程[3]。拓?fù)錁?gòu)建用于關(guān)閉網(wǎng)絡(luò)冗余節(jié)點,減少節(jié)點之間的鏈路通信;拓?fù)渚S護(hù)用于優(yōu)化網(wǎng)絡(luò)拓?fù)淦胶夤?jié)點之間的能耗。當(dāng)前研究使用最小連通支配集MCDS(Minimum Connected Dominating Set)構(gòu)造虛擬骨干樹作為延長網(wǎng)絡(luò)生命的主要拓?fù)錁?gòu)建方法[4],它將網(wǎng)絡(luò)節(jié)點分為活躍節(jié)點和普通節(jié)點?；钴S節(jié)點負(fù)責(zé)監(jiān)聽并轉(zhuǎn)發(fā)數(shù)據(jù),而普通節(jié)點進(jìn)入休眠以節(jié)約能量。然而,求解MCDS是典型的NP-hard問題,因此已經(jīng)有大量學(xué)者對該問題進(jìn)行了研究。

文獻(xiàn)[5]提出了令牌流技術(shù)對MCDS問題進(jìn)行數(shù)學(xué)建模,以最小網(wǎng)絡(luò)分發(fā)的令牌數(shù)作為目標(biāo)函數(shù),求解完畢后各個持有令牌的節(jié)點組成的集合即為MCDS。文獻(xiàn)[6]對文獻(xiàn)[5]進(jìn)行了改進(jìn),在目標(biāo)函數(shù)中引入節(jié)點的剩余能量作為約束條件,從而優(yōu)化了網(wǎng)絡(luò)的時間。上述算法依靠全局拓?fù)湟话隳軌虻玫捷^小的MCDS,然而,求解過程中需要節(jié)點之間的大量通信作為代價,同時求解的時間和空間復(fù)雜度較高,不適合冗余部署的密集型網(wǎng)絡(luò)。

EECDS[7]采用最大獨(dú)立集技術(shù)構(gòu)造連通支配集,初始時所有節(jié)點狀態(tài)為White,算法選擇一個初始節(jié)點s廣播Black消息;鄰域狀態(tài)為White的節(jié)點收到消息后,改變狀態(tài)為Grey并廣播Grey消息;Grey節(jié)點鄰域內(nèi)的White節(jié)點收到該消息后,將權(quán)值廣播出去并啟動超時競爭成為Black節(jié)點;如果White節(jié)點在超時內(nèi)收到了Black節(jié)點的Invite消息則成為Black節(jié)點并繼續(xù)廣播Black消息。算法由內(nèi)向外覆蓋網(wǎng)絡(luò),直到所有的黑色節(jié)點構(gòu)成一個彼此互不相連的最大獨(dú)立集。第二階段同樣從s開始廣播Blue消息;狀態(tài)為Grey的節(jié)點,更新權(quán)值并重新廣播消息競爭成為連通節(jié)點,如果在超時內(nèi)收到Black節(jié)點的Invite消息則成為連接節(jié)點。最終,所有Black節(jié)點和連接節(jié)點構(gòu)成連通支配集。Kim在文獻(xiàn)[8]中指出EECDS在連通節(jié)點的過程中會存在死鎖的問題,需要在執(zhí)行中增加一個處理條件。然而,EECDS產(chǎn)生的MCDS可能過大,文獻(xiàn)[9-10]利用剪枝縮小MCDS規(guī)模,即首先生成一個未經(jīng)優(yōu)化的MCDS,然后使用修剪規(guī)則去掉冗余節(jié)點。

A3[11]采用生成樹構(gòu)造連通支配集,Active節(jié)點廣播Hello消息搜集鄰居節(jié)點信息,鄰居節(jié)點收到消息后計算剩余能量和信號強(qiáng)度并回復(fù)一個父親認(rèn)知消息給上層Active節(jié)點;父節(jié)點收到回復(fù)后對子節(jié)點進(jìn)行排序,最終將節(jié)點等待時間列表廣播給鄰域子節(jié)點;等待時間結(jié)束后,子節(jié)點成為活躍節(jié)點并繼續(xù)在下一跳節(jié)點中搜索活躍節(jié)點。A3能夠得到較小的連通支配集規(guī)模,但是在構(gòu)建過程中每一個Active節(jié)點均需要向鄰居節(jié)點廣播一個排序后的等待時間列表,當(dāng)節(jié)點規(guī)模較大時這將使得發(fā)送的消息包將非常大,嚴(yán)重影響網(wǎng)絡(luò)的能效性[12]。A3G[13]對這方面進(jìn)行了改進(jìn),其采用了逆向構(gòu)建CDS樹的過程減少了部分通信開銷,降低了傳輸包的大小,但是算法的時間和空間復(fù)雜度還是較高。

EB-MCDS[14]將節(jié)點度和剩余能量作為節(jié)點的權(quán)值,優(yōu)先選擇權(quán)值較大的節(jié)點成為活躍節(jié)點,但是算法在構(gòu)造MCDS的過程中需要搜集二跳鄰域的節(jié)點信息,使得算法的信息復(fù)雜度達(dá)到了O(nΔ),因而只能應(yīng)用在規(guī)模較小的網(wǎng)絡(luò)中。

以上研究均假設(shè)區(qū)域內(nèi)的節(jié)點性能完全相同,這與實際網(wǎng)絡(luò)嚴(yán)重脫節(jié)。文獻(xiàn)[15]指出異構(gòu)WSNs可以分為計算異構(gòu)、鏈路異構(gòu)和能量異構(gòu),即網(wǎng)絡(luò)中可以存在不同計算能力、通信能力以及能量水平的節(jié)點。同時,拓?fù)渚S護(hù)對于網(wǎng)絡(luò)生存時間同樣產(chǎn)生重要影響,在惡劣環(huán)境下節(jié)點可能由于突發(fā)情況而失效,這就需要算法能夠動態(tài)重構(gòu)網(wǎng)絡(luò)。文獻(xiàn)[16]將拓?fù)淇刂婆c拓?fù)渚S護(hù)進(jìn)行區(qū)分,并指出選擇合適的拓?fù)渚S護(hù)策略將大大增加網(wǎng)絡(luò)的生命時間。為了使得研究更加貼近現(xiàn)實,本文考慮網(wǎng)絡(luò)中節(jié)點的通信半徑和能量水平存在異構(gòu)的情況下,提出了一種帶有拓?fù)渚S護(hù)機(jī)制的拓?fù)淇刂品椒ˋ3M,算法不僅以最小化連通支配集的數(shù)量作為主要目標(biāo),而且以較低的時間和消息復(fù)雜度最小化拓?fù)錁?gòu)建能耗,當(dāng)網(wǎng)絡(luò)不再最優(yōu)時,觸發(fā)拓?fù)渚S護(hù)對網(wǎng)絡(luò)重構(gòu),這一過程不斷循環(huán)直至運(yùn)行結(jié)束。

1 模型與A3G算法概述

1.1 網(wǎng)絡(luò)模型和問題描述

我們用圖G(V,E)表示異構(gòu)無線傳感器網(wǎng)絡(luò)模型,其中V表示N個傳感器節(jié)點集合{v1,v2,…,vN},E是由V中節(jié)點組成的通信鏈路集合,假設(shè)節(jié)點的最大通信半徑CTRmax(Critical Transmitting Range[17])可以不同,節(jié)點vi和vj之間存在鏈路當(dāng)且僅當(dāng)vi和vj相互處于對方的通信半徑內(nèi),即(vi,vj)∈E當(dāng)且僅當(dāng)d(vi,vj)≤min{Ri,Rj},其中d(vi,vj)表示節(jié)點vi與vj之間的歐式距離,min{Ri,Rj}為節(jié)點vi和vj的較小通信半徑。節(jié)點靜止部署在M×M的二維平面內(nèi),基站(Sink)部署在區(qū)域的中心位置(M/2,M/2),各個節(jié)點具有唯一的ID且能量可以異構(gòu),同時節(jié)點之間不需要使用GPS或其他定位算法獲得位置信息以節(jié)約能量。

下面對本文提出的拓?fù)淇刂扑惴ˋ3M在異構(gòu)網(wǎng)絡(luò)中所求解的問題進(jìn)行描述。假設(shè)節(jié)點集合V存在子集DS(DS?V),對于網(wǎng)絡(luò)中其他任意節(jié)點u(u∈V-DS),如果在節(jié)點u的通信半徑Ru內(nèi)至少存在一個DS中的節(jié)點v(v∈DS)且其通信半徑Rv≥d(u,v),則將DS中節(jié)點組成的集合稱為支配集。如果DS是連通的則DS為連通支配集。最小化生成的連通支配集中的數(shù)量即為算法所求解的異構(gòu)網(wǎng)絡(luò)中的最小連通支配集問題。

1.2 A3G算法

下面對A3G的性能進(jìn)行分析,算法主要分為鄰居節(jié)點發(fā)現(xiàn),鄰居信息交換和節(jié)點競爭3個過程:

①鄰居節(jié)點發(fā)現(xiàn):Sink節(jié)點以最大功率廣播Hello信息,鄰域內(nèi)節(jié)點收到信息后計算權(quán)值并繼續(xù)廣播Hello信息直到遍歷所有節(jié)點;該過程中,算法的時間和信息復(fù)雜度均為O(n)。

②鄰居信息交換:在鄰居節(jié)點發(fā)現(xiàn)階段,當(dāng)子節(jié)點收到父節(jié)點發(fā)送的Hello信息時,將向父節(jié)點回復(fù)一個包含節(jié)點ID和權(quán)值的信息。父節(jié)點收到信息后將其存儲以備在節(jié)點競爭時使用。該過程算法的信息復(fù)雜度為O(n);由于節(jié)點需要對鄰域內(nèi)節(jié)點的權(quán)值進(jìn)行排序,算法的時間復(fù)雜度為O(nlogn)。

③節(jié)點競爭過程:從葉節(jié)點開始,節(jié)點從候選列表中選擇權(quán)值最大的節(jié)點作為活躍節(jié)點,記為S。節(jié)點S在鄰域內(nèi)廣播Sleep信息并向存儲列表中權(quán)值最大的父節(jié)點發(fā)送骨干確認(rèn)信息。鄰居節(jié)點收到信息后設(shè)置一個超時timer,如果timer內(nèi)沒有收到其他節(jié)點的確認(rèn)消息,那么它將進(jìn)入休眠模式;否則,繼續(xù)向上層競爭直到Sink節(jié)點。這一過程中節(jié)點將發(fā)送2n的信息,同時算法的時間復(fù)雜度為O(n)。

綜上所述,在最壞情況下,A3G的時間和信息復(fù)雜度分別為O(nlogn)和O(4n)。同時,A3G只適用于同構(gòu)網(wǎng)絡(luò),沒有考慮到節(jié)點之間的異構(gòu),當(dāng)節(jié)點能量降低而不再適合作為骨干時,也沒有對拓?fù)渚S護(hù)過程進(jìn)行深入研究。針對以上問題,本文從拓?fù)錁?gòu)建與拓?fù)渚S護(hù)兩個方面對網(wǎng)絡(luò)進(jìn)行優(yōu)化。

2 A3M算法

2.1 拓?fù)錁?gòu)建

A3M將拓?fù)錁?gòu)建分為鄰居節(jié)點發(fā)現(xiàn)、鄰居節(jié)點競爭以及未覆蓋節(jié)點發(fā)現(xiàn)3個過程。初始時,網(wǎng)絡(luò)中節(jié)點的狀態(tài)為Initial;算法結(jié)束后,節(jié)點狀態(tài)將變成Active或Sleep。算法執(zhí)行過程如下:

①鄰居節(jié)點發(fā)現(xiàn)

在同構(gòu)網(wǎng)絡(luò)中,節(jié)點u收到鄰域內(nèi)節(jié)點v的消息后,即可以確定u,v處于通信半徑內(nèi),v同樣可以接收到u廣播的消息。本文考慮網(wǎng)絡(luò)中節(jié)點的通信半徑存在異構(gòu)的情況,因此需要兩輪的Hello信息交換確定鄰域內(nèi)節(jié)點。我們令Nr(u)表示節(jié)點u能夠收到的發(fā)送節(jié)點ID集合,初始時Nr(u)為空。在第一輪信息交換中,節(jié)點u將收到的節(jié)點ID存儲到Nr(u),并在第二輪消息交換中廣播出去。當(dāng)節(jié)點u收到節(jié)點v的Nr(v)后,通過判斷當(dāng)前節(jié)點u是否在Nr(v)中即可以確認(rèn)節(jié)點u,v是否可以進(jìn)行通信。

②鄰居節(jié)點競爭

節(jié)點競爭從Sink開始,廣播Dominate消息并改變節(jié)點狀態(tài)為Active。狀態(tài)為Initial的節(jié)點u收到節(jié)點v發(fā)送的信息后,將檢查v是否在鄰域N(u),如果v是鄰居節(jié)點則計算適應(yīng)度fitness并啟動與之成反比的定時器timer1競爭成為活躍節(jié)點。同時,將狀態(tài)改變?yōu)镃andidate并廣播Candidate信息表示節(jié)點成為候選節(jié)點。鄰域節(jié)點w收到Candidate消息判斷u是否在N(w)內(nèi),如果是鄰居節(jié)點則更新未覆蓋節(jié)點集合uncover(w)=N(w){v};否則,忽略該消息。

timer1內(nèi)節(jié)點u收到N(u)內(nèi)節(jié)點v的Dominate消息,即表示鄰居節(jié)點具有更好的fitness,節(jié)點u將狀態(tài)改變?yōu)镾leep Candidate并重置新的超時timer2。

③未覆蓋節(jié)點發(fā)現(xiàn)

狀態(tài)為Sleep Candidate的節(jié)點u等待時間timer2后,將查找uncover(u)是否還有未被覆蓋節(jié)點,如果存在則節(jié)點u改變?yōu)锳ctive并廣播Check Message;否則,將狀態(tài)改變?yōu)镾leep并進(jìn)入睡眠模式。狀態(tài)為Sleep Candidate鄰居節(jié)點v收到該消息,則重置timer2以增加等待時間,確保節(jié)點只有在必需時才成為活躍節(jié)點。

圖1 A3M拓?fù)錁?gòu)建運(yùn)行實例

圖1為A3M拓?fù)錁?gòu)建算法的具體運(yùn)行實例。圖1(a)中節(jié)點E雖然在活躍節(jié)點A的通信范圍內(nèi),但是A不能收到E發(fā)送的信息,因此E不是A的鄰居節(jié)點;圖1(b)中鄰域節(jié)點B成功競爭為活躍節(jié)點,而節(jié)點D進(jìn)入Sleep Candidate;圖1(d)中超時timer2結(jié)束,節(jié)點D由于鄰域內(nèi)存在未覆蓋的節(jié)點G而成為活躍節(jié)點,節(jié)點C進(jìn)入休眠狀態(tài);最終形成拓?fù)淙鐖D1(f)。

2.2 拓?fù)渚S護(hù)

拓?fù)渚S護(hù)是恢復(fù)、輪換、再生成拓?fù)涞倪^程,通常根據(jù)時間或能量等條件定義不同的維護(hù)策略,網(wǎng)絡(luò)中節(jié)點在拓?fù)錁?gòu)建后將啟動拓?fù)渚S護(hù)過程。如果節(jié)點的剩余能量小于閾值,節(jié)點將向基站發(fā)送Reconstruction Message(sendID,gatewayID,SinkID)請求網(wǎng)絡(luò)重建,并更新當(dāng)前節(jié)點的閾值,其中sendID表示發(fā)送節(jié)點ID,gatewayID表示下一跳節(jié)點ID,SinkID表示基站的ID。

Reconstruction Message沿著gatewayID向基站發(fā)送,如果當(dāng)前節(jié)點ID不等于SinkID,節(jié)點繼續(xù)選擇合適的gatewayID進(jìn)行轉(zhuǎn)發(fā);否則,表示信息到達(dá)基站。Sink節(jié)點對當(dāng)前網(wǎng)絡(luò)狀態(tài)評估后將Decision Message(flag,time)沿著MCDS對全網(wǎng)進(jìn)行廣播,其中flag表示是否重構(gòu)網(wǎng)絡(luò),time表示等待重構(gòu)的時延?；钴S節(jié)點將收到的Decision Message向普通節(jié)點轉(zhuǎn)發(fā),并在time后重構(gòu)拓?fù)洹?/p>

由于重構(gòu)拓?fù)渫ǔＰ枰拇罅康臅r間和能量,為了避免由于少量節(jié)點的失效引起全網(wǎng)的變動,Sink可以預(yù)先在拓?fù)錁?gòu)建中生成并存儲若干能夠覆蓋網(wǎng)絡(luò)但彼此不相交的MCDS集合,這些集合可能并非最優(yōu),但是能夠快速執(zhí)行輪換,我們稱之為網(wǎng)絡(luò)的靜態(tài)拓?fù)渚S護(hù)。如果在時間T內(nèi),Sink節(jié)點收到多個節(jié)點的Reconstruction請求,則證明當(dāng)前網(wǎng)絡(luò)已經(jīng)并非最優(yōu),需要動態(tài)重構(gòu)網(wǎng)絡(luò)。

2.3 適應(yīng)度函數(shù)

考慮網(wǎng)絡(luò)的異構(gòu)性同時最小化MCDS的數(shù)量,本文將節(jié)點相對剩余能量、節(jié)點之間的距離、節(jié)點的通信半徑以及在拓?fù)渚S護(hù)中被選擇為活躍節(jié)點的次數(shù)作為適應(yīng)度函數(shù)的參數(shù),具體公式如下:

(1)

其中,ω1,ω2,ω3,ω4表示對應(yīng)的權(quán)值,在初期進(jìn)行設(shè)定。Eu表示節(jié)點u的剩余能量,N(u)表示一跳鄰居節(jié)點,當(dāng)節(jié)點剩余能量在鄰域范圍內(nèi)最大時則越有可能成為活躍節(jié)點;d、Ru、Rmax分別表示當(dāng)前節(jié)點與上層活躍節(jié)點之間的距離、當(dāng)前節(jié)點的通信半徑以及節(jié)點的最大通信半徑,均可以由接收到信號的強(qiáng)度RSSI獲得;ActiveNum表示節(jié)點在拓?fù)渚S護(hù)中被選舉為骨干的次數(shù),Rounds則表示當(dāng)前已經(jīng)進(jìn)行的拓?fù)渚S護(hù)次數(shù),即節(jié)點被選擇為活躍節(jié)點的次數(shù)越多則其適應(yīng)度函數(shù)值越小。

3 性能分析

定理1如果初始WSNs是連通的,那么通過A3M拓?fù)錁?gòu)建算法形成的CDS也是連通的。

證明使用反證法進(jìn)行證明,假設(shè)拓?fù)錁?gòu)建后形成的CDS是非連通的,那么至少存在一個狀態(tài)為Initial的節(jié)點。算法從Sink節(jié)點起由內(nèi)向外覆蓋網(wǎng)絡(luò),Initial節(jié)點首先被標(biāo)記為Candidate,其中fitness較大且鄰域內(nèi)存在未覆蓋節(jié)點的節(jié)點在timer1后成為Active;而fitness較小的Candidate節(jié)點將在timer2后確認(rèn)是否有需要覆蓋的節(jié)點,并最終將狀態(tài)轉(zhuǎn)換為Sleep或Active。最終,所有節(jié)點被標(biāo)記為Active或Sleep。如果存在狀態(tài)為Initial的節(jié)點,說明初始的WSNs是非連通的,這與假設(shè)不符,得證。

定理2A3M拓?fù)錁?gòu)建算法的信息和時間復(fù)雜度均為O(n)。

證明在異構(gòu)網(wǎng)絡(luò)中鄰居節(jié)點的發(fā)現(xiàn)過程需要兩輪的信息交換確定鄰域內(nèi)的節(jié)點,算法復(fù)雜度為O(2)。鄰居節(jié)點競爭過程中,Initial節(jié)點收到父節(jié)點的Dominate消息后將回復(fù)O(1)的信息。如果節(jié)點的fitness在鄰域內(nèi)最大將在timer1后發(fā)送O(1)的消息;否則,在超時timer2后檢查鄰域內(nèi)是否存在尚未覆蓋的節(jié)點,如果存在則發(fā)送O(1)的消息包反之進(jìn)入休眠狀態(tài)。狀態(tài)為Active的節(jié)點將發(fā)送O(2)的信息,而Sleep節(jié)點最多發(fā)送O(1)的消息。在最壞情況下,算法在異構(gòu)網(wǎng)絡(luò)中的信息復(fù)雜度為O(4n)。同時,如果節(jié)點部署在同構(gòu)網(wǎng)絡(luò)中,由于在鄰居發(fā)現(xiàn)過程中僅僅需要一輪的信息交換,算法在最壞情況下的信息復(fù)雜度為O(3n)。此外,節(jié)點的計算不需要排序和發(fā)送大數(shù)據(jù)量的消息包,并且操作均能在常數(shù)時間內(nèi)完成,因此算法的時間復(fù)雜度為O(n)。

定理3當(dāng)節(jié)點能量達(dá)到閾值時,A3M拓?fù)渚S護(hù)過程的信息和時間復(fù)雜度均為O(n)。

證明網(wǎng)絡(luò)運(yùn)行一段時間后,當(dāng)節(jié)點的剩余能量小于閾值時,節(jié)點將以O(shè)(1)時間構(gòu)建Reconstruction Message并向Sink節(jié)點發(fā)送重構(gòu)網(wǎng)絡(luò)請求。消息沿著MCDS向基站傳遞,最壞情況下,該消息包將轉(zhuǎn)發(fā)O(n)到達(dá)基站。Sink節(jié)點根據(jù)當(dāng)前網(wǎng)絡(luò)狀況將執(zhí)行的拓?fù)渚S護(hù)策略和時延封裝在Decision Message,并沿著拓?fù)浞聪蜣D(zhuǎn)發(fā),因此拓?fù)渚S護(hù)發(fā)送的消息最多不會超過2n,其消息復(fù)雜度為O(n)。由于節(jié)點的消息發(fā)送和轉(zhuǎn)發(fā)操作均能在常數(shù)時間O(1)內(nèi)完成,因此整個拓?fù)渚S護(hù)過程的時間復(fù)雜度也為O(n)。

4 仿真實驗及分析

4.1 實驗環(huán)境及參數(shù)設(shè)置

仿真實驗將A3M與A3、A3G、EECDS、CDS-Rule-K[10]4個算法進(jìn)行比較,實驗采用文獻(xiàn)[18]中的能耗模型并用基于網(wǎng)絡(luò)事件驅(qū)動的仿真軟件Atarraya[19]進(jìn)行評估,實驗結(jié)果取自隨機(jī)生成的20個拓?fù)鋵嵗謩e運(yùn)行20次后的平均值,考慮到A3算法需要傳輸所有鄰居節(jié)點排序后的等待時間列表,我們將該消息包的大小設(shè)為100 Byte,其他消息包的大小設(shè)為40 Byte,其他實驗參數(shù)如表1所示。

仿真實驗從拓?fù)淇刂婆c拓?fù)渚S護(hù)兩個方面對算法進(jìn)行評估,拓?fù)錁?gòu)建考慮生成的活躍節(jié)點個數(shù)、信息的發(fā)送數(shù)量以及能量消耗比率3個方面的性能,并定義能耗比率為網(wǎng)絡(luò)中節(jié)點消耗的能量與初始能量的比值;拓?fù)渚S護(hù)則評估A3M在無拓?fù)渚S護(hù)、靜態(tài)拓?fù)渚S護(hù)、動態(tài)拓?fù)渚S護(hù)3種不同策略下的網(wǎng)絡(luò)運(yùn)行時間。

4.2 實驗結(jié)果分析

本節(jié)對實驗結(jié)果進(jìn)行分析,實驗1在保持節(jié)點數(shù)量不變的基礎(chǔ)上調(diào)整臨界傳輸范圍CTR改變節(jié)點度。如圖2所示,A3M產(chǎn)生的活躍節(jié)點數(shù)要少于其他算法的結(jié)果,這說明A3M執(zhí)行后能夠獲得更接近最優(yōu)值的解。隨著傳輸半徑的增大,各算法產(chǎn)生的活躍節(jié)點數(shù)都逐漸減少,這是由于臨界傳輸范圍的增加造成任意節(jié)點可通信范圍的增加,即節(jié)點度的增加使得單位活躍節(jié)點可支配的節(jié)點增多,因此最終需要的活躍節(jié)點數(shù)相比原來有所減少。

圖2 實驗1改變節(jié)點度時的活躍節(jié)點數(shù)

圖3與圖4分別顯示了各個算法在拓?fù)錁?gòu)建過程中發(fā)送的消息數(shù)和能耗比率情況,EECDS和CDS-Rule-K在確認(rèn)一個節(jié)點成為活躍節(jié)點時需要在節(jié)點之間交換大量的消息以做出決定,因此其發(fā)送的消息總量遠(yuǎn)遠(yuǎn)多于其他3種算法,而實驗顯示A3M所需要交互的消息數(shù)量最少,這是因為理論分析可知算法在最壞情況下僅僅需要發(fā)送4n的消息數(shù)量。同時從文獻(xiàn)[18]中的能耗模型中可知,節(jié)點的能量消耗與節(jié)點發(fā)送和接收消息的數(shù)據(jù)比特成正比,因此交互的消息數(shù)量越多所需要傳輸?shù)谋忍鼐驮蕉?這樣所產(chǎn)生的能耗自然也就增加了,這也是A3M在拓?fù)錁?gòu)建中消耗能量最少的原因。隨著節(jié)點度的增加A3M消耗的能量有所增加但基本穩(wěn)定,其能耗相比A3G和A3算法分別平均減少了20.3%和33.1%。

圖3 實驗1改變節(jié)點度時的發(fā)送消息數(shù)

圖4 實驗1改變節(jié)點度時的能耗比率

實驗2通過改變節(jié)點的數(shù)量來比較各類算法的性能。圖5～圖7顯示,節(jié)點密度的改變并不影響A3M以較少的信息、能耗代價獲得比A3G、A3、EECDS、CDS-Rule-K更少的活躍節(jié)點集。當(dāng)網(wǎng)絡(luò)由50個節(jié)點組成時,A3M算法平均需要19.2個節(jié)點以連通網(wǎng)絡(luò),相當(dāng)于38.4%的節(jié)點將成為活躍節(jié)點,這一數(shù)據(jù)隨著網(wǎng)絡(luò)節(jié)點的增加而減少,當(dāng)在250個節(jié)點的網(wǎng)絡(luò)中A3M算法僅僅需要9.8%的活躍節(jié)點數(shù)。A3M算法能夠獲得較小活躍節(jié)點數(shù)的原因主要在于其在鄰居節(jié)點發(fā)現(xiàn)階段獲得了局部拓?fù)涞乃泄?jié)點信息,然后通過本文定義的適應(yīng)度函數(shù)優(yōu)先選擇性能較優(yōu)的節(jié)點成為活躍節(jié)點,因而需要的活躍節(jié)點數(shù)較少。同時,我們發(fā)現(xiàn)隨著節(jié)點數(shù)量的增加產(chǎn)生的活躍節(jié)點數(shù)并不是一直增長,這是可以理解的,因為活躍節(jié)點達(dá)到一定數(shù)量時即可覆蓋整個網(wǎng)絡(luò),此時繼續(xù)增加節(jié)點數(shù)并不會引起活躍節(jié)點的持續(xù)增加。

圖5 實驗2改變節(jié)點數(shù)量時的活躍節(jié)點數(shù)

圖6 實驗2改變節(jié)點數(shù)量時的發(fā)送消息數(shù)

圖7 實驗2改變節(jié)點數(shù)量時的能耗比率

實驗3對A3M算法的拓?fù)渚S護(hù)策略進(jìn)行評估,節(jié)點每隔10個單位時間向Sink節(jié)點發(fā)送采集的數(shù)據(jù),節(jié)點的能量閾值記為0.2 J,不考慮數(shù)據(jù)融合。如圖8和圖9所示,無論是在稀疏網(wǎng)絡(luò)還是密集網(wǎng)絡(luò)中,本文提出的拓?fù)渚S護(hù)策略將延長網(wǎng)絡(luò)的運(yùn)行時間。其中,靜態(tài)拓?fù)渚S護(hù)策略所生成的連通支配集中的節(jié)點性能由最初決定,因此當(dāng)網(wǎng)絡(luò)運(yùn)行一段時間后其所使用的連通支配集的性能可能已經(jīng)并非最優(yōu),使得網(wǎng)絡(luò)運(yùn)行時間不如動態(tài)拓?fù)渚S護(hù)策略。圖8中顯示在稀疏網(wǎng)絡(luò)中,靜態(tài)拓?fù)渚S護(hù)策略在時間點16 679.2時開始陸續(xù)出現(xiàn)節(jié)點的死亡而導(dǎo)致通信覆蓋率下降,而這一現(xiàn)象在動態(tài)拓?fù)渚S護(hù)中則發(fā)生在時間點23 252.7。相比稀疏網(wǎng)絡(luò),在密集網(wǎng)絡(luò)中各個算法通信覆蓋率的下降趨勢有所減緩,從圖9中發(fā)現(xiàn)動態(tài)拓?fù)渚S護(hù)策略直到時間點55 861.5時才開始出現(xiàn)通信覆蓋率的下降,其相比無拓?fù)渚S護(hù)時的網(wǎng)絡(luò)生命時間得到了明顯的提高,而且下降趨勢相對于稀疏網(wǎng)絡(luò)而言更為平緩,這是因為當(dāng)節(jié)點密度足夠時個別節(jié)點的失效并不會顯著影響網(wǎng)絡(luò)的生存時間,及時運(yùn)行網(wǎng)絡(luò)的拓?fù)渚S護(hù)過程替換失效節(jié)點將極大改善網(wǎng)絡(luò)的性能。

圖8 實驗3稀疏網(wǎng)絡(luò)下A3M的覆蓋率變化

圖9 實驗3密集網(wǎng)絡(luò)下A3M的覆蓋率變化

5 結(jié)束語

本文提出了一種異構(gòu)網(wǎng)絡(luò)中的基于CDS樹的分布式拓?fù)淇刂品椒ˋ3M,算法從拓?fù)錁?gòu)建與拓?fù)渚S護(hù)兩個方面對網(wǎng)絡(luò)的能耗進(jìn)行優(yōu)化。在拓?fù)錁?gòu)建過程中,該算法不但減少了生成的活躍節(jié)點數(shù)量,而且降低了節(jié)點的時間和信息復(fù)雜度;當(dāng)運(yùn)行的網(wǎng)絡(luò)不再高效時,利用拓?fù)渚S護(hù)策略重構(gòu)網(wǎng)絡(luò)拓?fù)湟怨?jié)約能量。理論分析和仿真實驗進(jìn)一步證實,無論是將節(jié)點部署在稀疏還是密集的環(huán)境下,A3M算法相比A3G、A3、EECDS、CDS-Rule-K 4種算法在性能上均有了顯著的提高。應(yīng)該指出,本文在實現(xiàn)拓?fù)渚S護(hù)過程中僅僅考慮基于節(jié)點能量的拓?fù)渚S護(hù)策略而沒有考慮基于時間周期性輪換拓?fù)涞牟呗?而如何將這2種維護(hù)策略進(jìn)行結(jié)合也是今后需要進(jìn)一步完善的地方。

[1] Yick J,Mukherjee B,Ghosal D.Wireless Sensor Network Survey[J].Computer Networks,2008,52(12):2292-2330.

[2]Aziz A A,Sekercioglu Y A,Fitzpatrick P,et al.A Survey on Distributed Topology Control Techniques for Extending the Lifetime of Battery Powered Wireless Sensor Networks[J].IEEE Communications Surveys and Tutorials,2013,15(1):121-144.

[3]Labrador M A,Wightman P M.Topology Control in Wireless Sensor Networks[M].Berlin:Springer,2009:61-68.

[4]Liu Z,Wang B W,Guo L J.A Survey on Connected Dominating Set Construction Algorithm for Wireless Sensor Networks[J].Information Technology,2010,9(6):1081-1092.

[5]Wightman P M,Fabregas A,Labrador M A.An Optimal Solution to the MCDS Problem for Topology Construction in Wireless Sensor Networks[C]//IEEE Latin-American Conference on Communi-cations(LATINCOM),Bogota,Columbia,2010:1-6.

[6]洪榛,俞立,張貴軍,等.基于最小連通支配集的無線傳感網(wǎng)拓?fù)錁?gòu)建研究[J].電子與信息學(xué)報,2012,34(8):2000-2006.

[7]Zeng Y Y,Jia X H,He Y X.Energy Efficient Distributed Connected Dominating Sets Construction in Wireless Sensor Networks[C]//International Conference on Wireless Communica-tions and Mobile Computing,Vancouver,Canada,2006:797-802.

[8]Kim D,Wu Y,Li Y,et al.Constructing Minimum Connected Dominating Sets with Bounded Diameters in Wireless Networks[J].IEEE Transactions on Parallel and Distributed Systems,2009,20(2):147-157.

[9]Das A,Mandal C,Reade C,et al.An Improved Greedy Construction of Minimum Connected Dominating Sets in Wireless Networks[C]//IEEE Wireless Communications and Networking Conference(WCNC),Cancun,Mexico,2011:790-795.

[10]Wu J,Cardei M,Dai F,et al.Extended Dominating Set and Its Applications in Ad Hoc Networks Using Cooperative Communication[J].IEEE Transactions on Parallel and Distributed Systems,2006,17(8):851-864.

[11]Wightman P M,Labrador M A.A3:A Topology Control Algorithm for Wireless Sensor Networks[C].//IEEE Global Telecommuni-cations Conference,New Orleans,USA,2008:1-6.

[12]Feeney L M,Nilsson M.Investigating the Energy Consumption of a Wireless Network Interface in an Ad Hoc Networking Environment[C]//Proceedings of Twentieth Annual Joint Conference of the IEEE Computer and Communications Societies(Infocom 2001),Anchorage,USA,2001:1548-1557.

[13]仇昌琪,肖明波.基于反向生成CDS樹的無線傳感器網(wǎng)絡(luò)拓?fù)淇刂扑惴ㄑ芯縖J].傳感技術(shù)學(xué)報,2012,25(12):1737-1742.

[14]凌飛,吳振華.能量均衡的最小連通支配集分布式算法[J].傳感技術(shù)學(xué)報,2012,25(9):1316-1321.

[15]Yarvis M,Kushalnagar N,Singh H,et al.Exploiting Heterogeneity in Sensor Networks[C]//Proceedings of 24th Annual Joint Conference of the IEEE Computer and Communications Societies(IEEE Infocom),Miami,USA,2005:878-890.

[16]Wightman P M,Labrador M A.Topology Maintenance:Extending the Lifetime of Wireless Sensor Networks[J].IEEE Latin America Transactions,2010,8(4):469-475.

[17]Santi P.Topology Control in Wireless Ad hoc and Sensor Networks[M].England,John Wiley and Sons,2005:39-52.

[18]Heinzelman W B,Chandrakasan A P,Balakrishnan H.An Applica-tion-Specific Protocol Architecture for Wireless Microsensor Networks[J].IEEE Transactions on Wireless Communications,2002,1(4):660-670.

[19]Wightman P M,Labrador M A.Atarraya:A Simulation Tool to Teach and Research Topology Control Algorithms for Wireless Sensor Metworks[C]//Proceedings of 2nd International Conference on Simulation Tools and Techniques,Rome,Italy,2009:26-35.

馬晨明(1983-),男,浙江杭州人,浙江工業(yè)大學(xué)信息學(xué)院博士研究生,主要研究方向為無線傳感器網(wǎng)絡(luò)拓?fù)淇刂?

王萬良(1957-),男,江蘇高郵人,博士生導(dǎo)師。國家級教學(xué)名師、享受國務(wù)院特殊政府津貼、浙江工業(yè)大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院院長,研究方向為計算機(jī)自動化、無線網(wǎng)絡(luò);

洪榛(1983-),男,浙江臺州人,博士。浙江理工大學(xué)機(jī)械與自動控制學(xué)院講師,主要研究方向為無線傳感器網(wǎng)絡(luò)拓?fù)淇刂啤⒅悄芙煌?、?yōu)化調(diào)度。在國內(nèi)外重要期刊及會議上發(fā)表論文10余篇,申請發(fā)明專利10項(已授權(quán)3項),軟件著作權(quán)30余項。

ATopologyControlMethodBasedonCDSTreeinHeterogeneousWirelessSensorNetwork*

MAChenming1,WANGWanliang2*,HONGZhen3

(1.College of Information Engineering,Zhejiang University of Technology,Hangzhou 310023,China;2.College of Computer Science and Technology,Zhejiang University of Technology,Hangzhou 310023,China;3.Faculty of Mechanical Engineering and Automation,Zhejiang Sci-Tech University,Hangzhou 310018,China)

Topology Control is a key strategy to save energy and extend the lifetime of wireless sensor networks.In view of the problem that existing topology control methods mainly focus on the homogeneous network to research on topology construction or topology maintenance separately,a distributed topology control algorithm A3M in the heterogeneous network is presented that contains both process.Topology construction is based on the Minimum Connected Dominating Set concept to construct the virtual backbone tree,which turns off redundant nodes to save energy while ensuring the network connectivity.Topology maintenance is related with the evaluation of the performance of the network,and changes the topology to maintain the stable operation of the network when the existing network performance degrades significantly.Theoretical analysis and simulation experiments confirm that our algorithm can reduce the energy consumption of topology construction and extend the network lifetime with low time and message complexity.

heterogeneous wireless sensor network;topology control;A3M algorithm;topology construction;topology maintenance;minimum connected dominating set

項目來源:國家自然科學(xué)基金項目(61304256,61379123);“十二五”國家科技支撐計劃項目(2012BAD10B01);浙江省自然科學(xué)基金項目(LQ13F030013);浙江省教育廳項目(Y201327006)

2014-03-18修改日期:2014-05-08

10.3969/j.issn.1004-1699.2014.06.020

TP393

:A

:1004-1699(2014)06-0814-07