耿 鵬,郝慧珍,柳 艷,葉子馨

(1.南京工程學(xué)院信息與通信工程學(xué)院,江蘇 南京 211167;2.南京工程學(xué)院數(shù)理學(xué)院,江蘇 南京 211167)

0 引言

無線傳感器網(wǎng)絡(luò)(wireless sensor networks,WSN)在軍事領(lǐng)域里的應(yīng)用環(huán)境通常十分惡劣,且是無人值守的[1-2]。WSN由大量的傳感器設(shè)備組成,這些傳感器設(shè)備由電池供電。在無人值守條件下,電池很難再次充電或更換。因此,采取相應(yīng)措施進行能量均衡以延長網(wǎng)絡(luò)生命周期是WSN面臨的最重要挑戰(zhàn)之一。在此方面的研究中,利用相應(yīng)的拓撲控制策略來減少節(jié)點能量均衡是一種關(guān)鍵技術(shù)。以往的研究往往將拓撲控制看作一個單一的過程,注重了拓撲構(gòu)建與重構(gòu),而忽略了拓撲維護的重要性。近年來,拓撲維護逐漸被重視,取得了一定的研究成果。文獻[3]將功率控制技術(shù)引入到拓撲維護之中,提出了一種基于功率自適應(yīng)的動態(tài)拓撲維護算法,該算法節(jié)省了傳感器節(jié)點的平均發(fā)射功率,但由于需要實時維護全局網(wǎng)絡(luò)的功率信息,其所產(chǎn)生的網(wǎng)絡(luò)開銷較大,且收斂時間較長。文獻[4]首先基于節(jié)點剩余能量對網(wǎng)絡(luò)進行拓撲構(gòu)建,再利用收發(fā)控制消息來判斷網(wǎng)絡(luò)拓撲結(jié)構(gòu)是否發(fā)生變化,最后根據(jù)變化的因素設(shè)計拓撲維護方法。該方法可以看作是基于能量觸發(fā)的拓撲維護,觸發(fā)條件較為單一。文獻[5]通過自適應(yīng)調(diào)整拓撲控制消息,提出了一種低開銷的拓撲維護算法,提高了優(yōu)化鏈路狀態(tài)路由協(xié)議的性能。該算法在鄰居發(fā)現(xiàn)策略方面產(chǎn)生了較多的冗余,對網(wǎng)絡(luò)性能有一定的影響。文獻[6]利用博弈算法在節(jié)點密度較大的區(qū)域進行再博弈、再分割,選出新的簇頭,在節(jié)點密度較小區(qū)域進行多簇合并,以達到均衡節(jié)點能耗的目的。該算法可以看作是基于密度的拓撲維護,其既要實時探測瓶頸節(jié)點,又要判斷區(qū)域密度,增加了網(wǎng)絡(luò)開銷。文獻[7]分析了網(wǎng)絡(luò)生命周期和節(jié)點剩余能量、節(jié)點間距離的關(guān)系,據(jù)此提出了一種網(wǎng)絡(luò)拓撲結(jié)構(gòu)動態(tài)演化的模型,提高了無標度網(wǎng)絡(luò)的生命周期。該模型本質(zhì)上是基于能量和節(jié)點密度的拓撲重構(gòu),無拓撲維護過程。文獻[8—9]通過拓撲控制技術(shù)來增加網(wǎng)絡(luò)幸存節(jié)點數(shù)和減少因級聯(lián)失效而產(chǎn)生的故障節(jié)點數(shù),此技術(shù)并沒有考慮到在拓撲構(gòu)建時簡化網(wǎng)絡(luò)結(jié)構(gòu)。文獻[10—12]在保證覆蓋率的前提下,使部分節(jié)點處于休眠狀態(tài),以減少能量消耗,但此方法沒有引入拓撲維護技術(shù),在節(jié)點能量均衡方面較為缺乏。文獻[13—15]研究了網(wǎng)絡(luò)自愈技術(shù),當發(fā)現(xiàn)網(wǎng)絡(luò)中存在覆蓋漏洞時,便啟動相應(yīng)算法進行修補,由于是一種查漏補缺策略,此類技術(shù)對于數(shù)據(jù)敏感度較高的軍事應(yīng)用并不適合。

從上述內(nèi)容可以看出,目前對拓撲控制技術(shù)的研究一是存在將拓撲重構(gòu)與拓撲維護相混淆的問題,二是存在拓撲構(gòu)建階段無簡化過程的問題,三是存在拓撲維護算法復(fù)雜,增加了網(wǎng)絡(luò)開銷的問題。據(jù)此,本文在利用生成樹算法進行拓撲簡化的基礎(chǔ)上,提出一種基于能量均衡的混合拓撲維護策略,以達到實現(xiàn)WSN節(jié)點能量均衡,延長生命周期目的。

1 拓撲構(gòu)建算法與拓撲維護策略選擇

通過對文獻[3—15]的總結(jié),可將惡劣環(huán)境下的無線傳感器網(wǎng)絡(luò)部署與拓撲控制分為三個階段:第一,在目標區(qū)域中隨機撒下多個傳感器節(jié)點,并進入網(wǎng)絡(luò)初始化階段,在該階段,考慮到位置未知網(wǎng)絡(luò),每個傳感器節(jié)點發(fā)現(xiàn)鄰居,然后建立通信路徑,并形成初始拓撲結(jié)構(gòu);第二,創(chuàng)建一個新的簡化拓撲,稱之為拓撲構(gòu)建階段,在這一階段,基于初始拓撲結(jié)構(gòu)形成連接支配集(connection dominating set,CDS),以構(gòu)建確保連接性和高覆蓋率的虛擬骨干網(wǎng)絡(luò)(virtual backbone network,VBN),VBN中的節(jié)點處于喚醒狀態(tài),而其他節(jié)點處于休眠狀態(tài);第三,VBN運行一定的時間,直到時間片到或某些節(jié)點的能量水平低于某個閾值時,網(wǎng)絡(luò)返回到拓撲構(gòu)建階段以建立新的VBN。在WSN的生命周期內(nèi),此循環(huán)將重復(fù)多次,稱之為拓撲維護階段。

1.1 拓撲構(gòu)建算法

在拓撲構(gòu)建階段,常用的算法包括:A3[16],A3Cov[17],EECDS[18]和CDS Rule K[19]。其中,A3和A3Cov基于生成樹(spanning tree,ST)算法[20],EECDS基于最大獨立集(maximum independent set,MIS)算法[21],CDS Rule K基于連通支配集(connected dominating set,CDS)算法[22]。在WSN的拓撲構(gòu)建中,利用上述算法進行拓撲構(gòu)建完成后,就形成了不同類型的VBN。從文獻[23—24]的對比分析中可以看出,在相同網(wǎng)絡(luò)初始化條件下,A3Cov在拓撲構(gòu)建階段激活了更多節(jié)點,使得覆蓋率性能最佳,但帶來的缺點是網(wǎng)絡(luò)生命周期大大縮短。A3,EECDS和CDS Rule K的覆蓋性能相似,但A3在同一時間段內(nèi)的網(wǎng)絡(luò)剩余能量性能最佳。根據(jù)圖1所示的隨機網(wǎng)絡(luò)部署,將匯聚結(jié)點(Sink)置于矩形區(qū)域的中心,傳感節(jié)點通信半徑設(shè)置為100 m,感知半徑設(shè)置為20 m,使用A3和A3Cov算法構(gòu)建的VBN如圖2和圖3所示。

圖1 隨機網(wǎng)絡(luò)部署Fig.1 Random network deployment

圖2 利用A3算法構(gòu)建的VBNFig.2 VBN constructed by A3 algorithm

圖3 利用A3Cov算法構(gòu)建的VBNFig.3 VBN constructed by A3Cov algorithm

將各算法挑選出來的骨干節(jié)點連接起來便形成了VBN,其他節(jié)點暫時處于休眠狀態(tài)。圖中黑色區(qū)域表示能量覆蓋區(qū)域,白色區(qū)域表示能量空穴,淺色區(qū)域表示感知覆蓋區(qū)域?？梢钥吹?A3Cov算法在能量覆蓋和感知覆蓋方面表現(xiàn)最好,但其激活的節(jié)點數(shù)卻遠多于A3算法。A3利用較少的活動節(jié)點保證了區(qū)域基本覆蓋,有利于生命周期的延長。本文將選擇A3算法進行拓撲構(gòu)建。

1.2 拓撲維護策略

在拓撲維護階段,需要監(jiān)控網(wǎng)絡(luò)拓撲狀態(tài),并在適當時候觸發(fā)新的拓撲構(gòu)建。拓撲構(gòu)建和拓撲維護之間的循環(huán)將在生命周期內(nèi)重復(fù)多次。因此,拓撲維護可以定義為當拓撲結(jié)構(gòu)不再最佳時,局部修改或全局重新創(chuàng)建網(wǎng)絡(luò)拓撲的過程。

從拓撲構(gòu)建階段進入拓撲維護階段所需要的觸發(fā)條件包括時間片到、達到節(jié)點能量閾值、達到故障節(jié)點數(shù)和平均節(jié)點度觸發(fā)等,具體描述如下。

1) 基于時間的拓撲維護:設(shè)置一個時間片,時間片到時,拓撲維護算法將終止當前簡化拓撲,并調(diào)用拓撲構(gòu)建算法來創(chuàng)建新的拓撲。定義拓撲構(gòu)建集合中的節(jié)點處于就緒狀態(tài),顯然,網(wǎng)絡(luò)中有3種節(jié)點狀態(tài):就緒狀態(tài)、運行狀態(tài)和休眠狀態(tài)。網(wǎng)絡(luò)中每個節(jié)點狀態(tài)描述如圖4所示。

圖4 節(jié)點狀態(tài)轉(zhuǎn)移圖Fig.4 Node state transition

2) 基于能量的拓撲維護:每當節(jié)點達到臨界能量閾值時,拓撲維護算法就會終止當前簡化拓撲,并調(diào)用拓撲構(gòu)建算法來創(chuàng)建新的拓撲。網(wǎng)絡(luò)中仍然具有圖4所示的3種節(jié)點狀態(tài),不同的是,節(jié)點的狀態(tài)從“運行狀態(tài)”轉(zhuǎn)變?yōu)椤靶菝郀顟B(tài)”的條件是“任一節(jié)點能量低于閾值”。

3) 基于故障的拓撲維護:當一個或多個節(jié)點發(fā)生故障時,會觸發(fā)更改當前拓撲的過程。顯然,此策略需要故障檢測和通知方法的支持,將形成新的網(wǎng)絡(luò)開銷。

4) 基于密度的拓撲維護:節(jié)點度可用于描述網(wǎng)絡(luò)密度,在網(wǎng)絡(luò)節(jié)點平均度降低到一定程度后觸發(fā)改變當前拓撲的過程。該方法需要實時計算網(wǎng)絡(luò)的節(jié)點度,同樣也增加了網(wǎng)絡(luò)開銷。

另外,拓撲維護的最終目標是延長網(wǎng)絡(luò)壽命。在設(shè)計過程中,必須考慮以下方面。

1) 動態(tài)拓撲維護:拓撲維護可分為靜態(tài)方法和動態(tài)方法。靜態(tài)方法將拓撲信息存儲在節(jié)點存儲器中,并在需要時打開。動態(tài)方法是僅當網(wǎng)絡(luò)運行中觸發(fā)某個閾值條件時才構(gòu)建拓撲。靜態(tài)方法需要大量內(nèi)存來存儲所有預(yù)先計算的拓撲,但是WSN的節(jié)點設(shè)備內(nèi)存是有限的,因此應(yīng)考慮動態(tài)拓撲維護。

2) 低開銷:拓撲維護不應(yīng)包含太多控制數(shù)據(jù)包。如基于能量、故障和密度的拓撲維護方法,均需要實現(xiàn)通知機制。因此,為了降低網(wǎng)絡(luò)開銷,上述三種方法不能全部考慮。

3) 低復(fù)雜性:拓撲維護中使用的算法必須簡單。顯然,基于時間的拓撲維護算法是最簡單的。

4) 能量均衡:當某些節(jié)點能量消耗到一定程度時,應(yīng)該允許它們休眠一段時間,以便所有節(jié)點都能均衡地參與網(wǎng)絡(luò)。在這方面,基于能量的拓撲維護算法是合適的。

2 基于能量均衡的混合拓撲維護策略

綜上,本文選擇A3算法進行拓撲構(gòu)建,考慮到無線傳感器網(wǎng)絡(luò)在惡劣環(huán)境下的應(yīng)用場景,提出一種時間和能量混合拓撲維護策略,以達到實現(xiàn)節(jié)點能量均衡的目的。

2.1 拓撲構(gòu)建階段

A3算法生成樹的過程包括3個階段:鄰居發(fā)現(xiàn)、子節(jié)點選擇和二次選擇。其中在鄰居發(fā)現(xiàn)階段,節(jié)點的狀態(tài)權(quán)值Mx,y描述為

(1)

式中:x是y的后一跳節(jié)點,WE是節(jié)點剩余能量權(quán)值,Ex是節(jié)點x的剩余能量,Emax是節(jié)點x初始化的最大能量,WD是上下跳節(jié)點之間的距離權(quán)值,Ry是節(jié)點x從節(jié)點y接收到的信號強度,Rmin為確保兩個節(jié)點連接的最小信號強度?？梢钥闯?該公式優(yōu)先考慮那些具有更高能量且距離父節(jié)點更遠的節(jié)點作為子節(jié)點,期望構(gòu)建具有更少節(jié)點和更好覆蓋的樹。

2.2 基于時間和能量的混合拓撲維護

在惡劣環(huán)境中,節(jié)點能量是極為寶貴的資源,而拓撲維護作為一種能量管理策略,可以幫助節(jié)點有效地利用能量,延長網(wǎng)絡(luò)生命周期,并提高網(wǎng)絡(luò)性能和可靠性。基于時間和基于能量的拓撲維護算法是較為有效的拓撲維護方法。其中,基于時間的方法主要關(guān)注時間片的長度,在時間片結(jié)束時進行拓撲維護,維護網(wǎng)絡(luò)的穩(wěn)定性和效率。而基于能量的方法則主要基于節(jié)點的能量消耗情況來進行拓撲維護,及時使能量消耗過大的節(jié)點進入休眠狀態(tài),并重新構(gòu)建拓撲結(jié)構(gòu),從而延長節(jié)點生命周期,提高網(wǎng)絡(luò)性能和效率。

本文混合了基于時間和基于能量的方法進行拓撲維護,即當節(jié)點能量消耗到一定閾值或網(wǎng)絡(luò)運行到時間片結(jié)束時,拓撲維護算法終止當前的拓撲結(jié)構(gòu),并再次調(diào)用拓撲構(gòu)建算法以創(chuàng)建新的網(wǎng)絡(luò)結(jié)構(gòu)。其處理流程如圖5所示。

圖5 基于混合策略的拓撲維護流程圖Fig.5 Hybrid-based topology maintenance flowchart

對于WSN,由普通節(jié)點收集的所有信息都以多跳形式傳輸?shù)絊ink節(jié)點,因此,Sink節(jié)點附近的普通節(jié)點的通信任務(wù)是最重的。本文在進行初始化時,網(wǎng)絡(luò)處于全連接狀態(tài),并且生命周期被定義為從網(wǎng)絡(luò)運行開始直到Sink節(jié)點成為孤立節(jié)點?；跁r間和基于能量的拓撲維護的主要目的是構(gòu)建簡化的主干結(jié)構(gòu),以便可以用較少的活動節(jié)點來獲取較大范圍的數(shù)據(jù)收集。基于此,將“生命周期”、“活動節(jié)點數(shù)”和“通信覆蓋率”的性能指標定義如下:

1) 生命周期:從網(wǎng)絡(luò)運行開始到Sink節(jié)點成為孤立節(jié)點所經(jīng)歷的時間。

2) 活動節(jié)點數(shù):可以與處于運行狀態(tài)的Sink節(jié)點通信的普通節(jié)點數(shù)量。顯然,它可以用來分析生命周期,當進行過新的拓撲構(gòu)建后,活動節(jié)點數(shù)仍為零時,標志著生命周期的結(jié)束。

3) 通信覆蓋率:該度量定義為活動節(jié)點的覆蓋面積與目標區(qū)域面積的比率。

3 仿真分析

在600 m×600 m的區(qū)域內(nèi),于中心位置部署一個Sink節(jié)點,并另外隨機部署100個普通節(jié)點。網(wǎng)絡(luò)運行過程中,節(jié)點發(fā)送和接收1 bit數(shù)據(jù)所消耗的能量分別表示為ETbit和ERbit,具體描述為

ETbit=ERbit+Eamp·(π·r2),

(2)

ERbit=Eelect,

(3)

式中:r表示節(jié)點通信半徑,Eamp是功率放大器消耗的能量密度,Eelect為電路損耗能量。

本文在Java平臺下,基于時間和能量控制策略,對A3拓撲構(gòu)建下的活動節(jié)點數(shù)和通信覆蓋率進行了對比。其參數(shù)設(shè)置如表1所示。

表1 模擬參數(shù)Tab.1 Simulation parameters

在拓撲維護階段,混合了基于時間和能量的策略,即當節(jié)點達到臨界能量閾值200 mJ或網(wǎng)絡(luò)在運行1 000 s時(即時間片設(shè)置為1 000 s),終止當前的拓撲結(jié)構(gòu)并調(diào)用A3拓撲構(gòu)建算法以創(chuàng)建新的拓撲。節(jié)點從“運行狀態(tài)”變?yōu)椤靶菝郀顟B(tài)”的條件是“時間片到或節(jié)點能量低于閾值”。在表1的模擬參數(shù)下,基于時間控制的A3、基于能量控制的A3和基于混合控制的A3性能比較如圖6—圖7所示。

圖6 不同控制策略下的生命周期比較Fig.6 Lifetime comparison based on different control strategies

圖7 不同控制策略下的通信覆蓋率比較Fig.7 Communication coverage comparison based on different control strategies

圖6顯示的是網(wǎng)絡(luò)活動節(jié)點數(shù)隨時間的變化,當活動節(jié)點數(shù)完全降低到0時,生命周期結(jié)束。可以看出,基于時間控制的A3和基于能量控制的A3的壽命在大約8 300 s和9 500 s時結(jié)束。基于混合控制的A3在12 000 s時結(jié)束。同時,在網(wǎng)絡(luò)運行中,基于混合控制的A3算法中的活動節(jié)點的數(shù)量總是比其他算法多。

圖7顯示的是通信覆蓋率隨時間的變化。在網(wǎng)絡(luò)運行初期,基于混合控制的A3通信覆蓋率達到97%,優(yōu)于另外兩種拓撲控制策略。WSN對目標區(qū)域的通信覆蓋必須要達到一定比例,否則其采集的數(shù)據(jù)參考價值將降低很多。本文以實現(xiàn)90%以上的通信覆蓋率作為標準。從圖7可以看出,基于混合控制的A3算法在覆蓋率閾值內(nèi)的時間為4 800 s,優(yōu)于基于時間控制的A3(大約2 000 s)和基于能量控制的A3(約4 000 s)。

仿真結(jié)果表明,本文所提出的混合拓撲維護策略使網(wǎng)絡(luò)生命周期最大提升了44.6%,90%覆蓋率結(jié)束時間最大增加了1.4倍,表明在基于時間和能量的混合拓撲維護策略下,網(wǎng)絡(luò)性能有較大提升,具體如表2所示。

表2 不同策略下的網(wǎng)絡(luò)性能Tab.2 Network performance based on different strategies

4 結(jié)論

本文針對現(xiàn)階段無線傳感器網(wǎng)絡(luò)中降低能耗以延長網(wǎng)絡(luò)生命周期的相關(guān)研究,指出了其在無人值守的特殊環(huán)境下應(yīng)用的局限性?；诖?將惡劣環(huán)境下的無線傳感器網(wǎng)絡(luò)部署與拓撲控制分為網(wǎng)絡(luò)初始化、拓撲構(gòu)建和拓撲維護3個階段。在隨機部署和虛擬骨干網(wǎng)絡(luò)構(gòu)建的前提下,提出一種時間和能量混合拓撲維護策略。通過在Java平臺上的仿真,對基于時間控制的A3、基于能量控制的A3和基于混合控制的A3算法進行活動節(jié)點數(shù)和通信覆蓋率的性能比較。結(jié)果表明,基于混合控制的拓撲構(gòu)建算法性能最優(yōu),能夠更好地降低網(wǎng)絡(luò)能量消耗,為諸如軍事領(lǐng)域中惡劣環(huán)境下的無線傳感器網(wǎng)絡(luò)部署和拓撲控制提供了參考。