無線傳感器網絡能量均衡混合拓撲維護策略

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

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

0 引言

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

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

1 拓撲構建算法與拓撲維護策略選擇

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

1.1 拓撲構建算法

在拓撲構建階段,常用的算法包括: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的拓撲構建中,利用上述算法進行拓撲構建完成后,就形成了不同類型的VBN。從文獻[23—24]的對比分析中可以看出,在相同網絡初始化條件下,A3Cov在拓撲構建階段激活了更多節點,使得覆蓋率性能最佳,但帶來的缺點是網絡生命周期大大縮短。A3,EECDS和CDS Rule K的覆蓋性能相似,但A3在同一時間段內的網絡剩余能量性能最佳。根據圖1所示的隨機網絡部署,將匯聚結點(Sink)置于矩形區域的中心,傳感節點通信半徑設置為100 m,感知半徑設置為20 m,使用A3和A3Cov算法構建的VBN如圖2和圖3所示。

圖1 隨機網絡部署Fig.1 Random network deployment

圖2 利用A3算法構建的VBNFig.2 VBN constructed by A3 algorithm

圖3 利用A3Cov算法構建的VBNFig.3 VBN constructed by A3Cov algorithm

將各算法挑選出來的骨干節點連接起來便形成了VBN,其他節點暫時處于休眠狀態。圖中黑色區域表示能量覆蓋區域,白色區域表示能量空穴,淺色區域表示感知覆蓋區域。可以看到,A3Cov算法在能量覆蓋和感知覆蓋方面表現最好,但其激活的節點數卻遠多于A3算法。A3利用較少的活動節點保證了區域基本覆蓋,有利于生命周期的延長。本文將選擇A3算法進行拓撲構建。

1.2 拓撲維護策略

在拓撲維護階段,需要監控網絡拓撲狀態,并在適當時候觸發新的拓撲構建。拓撲構建和拓撲維護之間的循環將在生命周期內重復多次。因此,拓撲維護可以定義為當拓撲結構不再最佳時,局部修改或全局重新創建網絡拓撲的過程。

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

1) 基于時間的拓撲維護:設置一個時間片,時間片到時,拓撲維護算法將終止當前簡化拓撲,并調用拓撲構建算法來創建新的拓撲。定義拓撲構建集合中的節點處于就緒狀態,顯然,網絡中有3種節點狀態:就緒狀態、運行狀態和休眠狀態。網絡中每個節點狀態描述如圖4所示。

圖4 節點狀態轉移圖Fig.4 Node state transition

2) 基于能量的拓撲維護:每當節點達到臨界能量閾值時,拓撲維護算法就會終止當前簡化拓撲,并調用拓撲構建算法來創建新的拓撲。網絡中仍然具有圖4所示的3種節點狀態,不同的是,節點的狀態從“運行狀態”轉變為“休眠狀態”的條件是“任一節點能量低于閾值”。

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

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

另外,拓撲維護的最終目標是延長網絡壽命。在設計過程中,必須考慮以下方面。

1) 動態拓撲維護:拓撲維護可分為靜態方法和動態方法。靜態方法將拓撲信息存儲在節點存儲器中,并在需要時打開。動態方法是僅當網絡運行中觸發某個閾值條件時才構建拓撲。靜態方法需要大量內存來存儲所有預先計算的拓撲,但是WSN的節點設備內存是有限的,因此應考慮動態拓撲維護。

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

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

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

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

綜上,本文選擇A3算法進行拓撲構建,考慮到無線傳感器網絡在惡劣環境下的應用場景,提出一種時間和能量混合拓撲維護策略,以達到實現節點能量均衡的目的。

2.1 拓撲構建階段

A3算法生成樹的過程包括3個階段:鄰居發現、子節點選擇和二次選擇。其中在鄰居發現階段,節點的狀態權值Mx,y描述為

(1)

式中:x是y的后一跳節點,WE是節點剩余能量權值,Ex是節點x的剩余能量,Emax是節點x初始化的最大能量,WD是上下跳節點之間的距離權值,Ry是節點x從節點y接收到的信號強度,Rmin為確保兩個節點連接的最小信號強度。可以看出,該公式優先考慮那些具有更高能量且距離父節點更遠的節點作為子節點,期望構建具有更少節點和更好覆蓋的樹。

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

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

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

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

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

1) 生命周期:從網絡運行開始到Sink節點成為孤立節點所經歷的時間。

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

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

3 仿真分析

在600 m×600 m的區域內,于中心位置部署一個Sink節點,并另外隨機部署100個普通節點。網絡運行過程中,節點發送和接收1 bit數據所消耗的能量分別表示為ETbit和ERbit,具體描述為

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

(2)

ERbit=Eelect,

(3)

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

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

表1 模擬參數Tab.1 Simulation parameters

在拓撲維護階段,混合了基于時間和能量的策略,即當節點達到臨界能量閾值200 mJ或網絡在運行1 000 s時(即時間片設置為1 000 s),終止當前的拓撲結構并調用A3拓撲構建算法以創建新的拓撲。節點從“運行狀態”變為“休眠狀態”的條件是“時間片到或節點能量低于閾值”。在表1的模擬參數下,基于時間控制的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顯示的是網絡活動節點數隨時間的變化,當活動節點數完全降低到0時,生命周期結束。可以看出,基于時間控制的A3和基于能量控制的A3的壽命在大約8 300 s和9 500 s時結束。基于混合控制的A3在12 000 s時結束。同時,在網絡運行中,基于混合控制的A3算法中的活動節點的數量總是比其他算法多。

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

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

表2 不同策略下的網絡性能Tab.2 Network performance based on different strategies

4 結論

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