無線傳感器網絡能量優化策略研究*

施開林，江 虹

（西南科技大學 信息工程學院，四川 綿陽 621010）

0 引 言

無線傳感器網絡（Wireless Sensor Network）是由部署在監測區域內的低成本﹑低功耗﹑具備感知﹑存儲和無線通信能力的大量傳感器節點通過自組織方式形成的網絡[1]。由于網絡節點由電池供電，導致其自身能量有限。如何降低節點的能量消耗與延長網絡的生存時間，已成為當前研究的熱點[2]。從單個節點的能量消耗途徑來看，其能量消費可分為通信消費和計算消費兩部分[3]。

文獻[4]基于LEACH[5]，根據簇頭的期望轉發負荷來調整簇大小，使得所有簇頭的能耗接近，網絡能量消耗均衡，但其使用到基站單跳的通信方式會造成遠離基站的節點因通信距離過長率先死亡。文獻[6]在LEACH協議基礎上，提出一種基于跨層功率控制的按需路由算法，通過按需建立多個不同功率級的路由來降低能量消耗，但未考慮網絡整體的能量均衡。文獻[7]運用遺傳算法在兩層網絡中尋找路由中間節點，以探尋優化路徑，雖然設計并未針對無線傳感器網絡，但設計思想值得借鑒。本文在LEACH路由協議的基礎上，首先提出一種基于遺傳算法的全新分簇機制，并改進了簇頭選舉方式；其次，改變原有的單跳傳輸方式為簇間多跳，并基于跨層設計，結合網絡層和MAC層制定聯合選路策略。

1 網絡模型

在WSN中，獲得監測數據的傳感器節點為源節點，其數據經過多跳傳輸到匯聚節點（Sink Node）或基站（Base Station），再通過互聯網或衛星到達管理節點或用戶。本文將WSN的監測區域進行集群分組（稱為簇），每個簇選出一個簇頭節點（Cluster Head）負責簇內節點和基站的通信。

作如下假設和定義：

（1）網絡中任意節點初始能量相等，且有唯一的識別編號(1,2,3…n)，均勻分布于監測區。

（2）所有節點位置固定，坐標為(xi,yi)，能量有限；基站固定，位置為(xsink, ysink)，能量不受限。

（3）鏈路是對稱的，節點可互相傳輸數據。

（4）所有節點都能調整自己的發射功率。

（5）每個節點周期執行數據采集任務，并始終有數據傳送至基站。

2 基于GA的分簇策略

2.1 分簇思想描述

在LEACH基礎上做以下兩點改進：

（1）由于文獻[8]證明了合理的拓撲結構可以使得形成的簇在整體上功耗較低，達到節省能量的目的，所以綜合考慮節點的能量信息﹑簇頭數目﹑節點之間的距離，運用遺傳算法控制和優化全局簇結構的生成。

（2）采用全新的簇頭候選機制，即在簇的形成階段，簇頭會根據簇內其他非簇頭節點傳輸的數據包判斷其能量強度，選擇能量最高的作為候選簇頭，以減少重新分簇的數，降低頻繁分簇帶來的網絡整體能耗。

2.2 算法流程描述

設計中，基站在獲取所有節點的狀態信息后，采用指定的編碼方式構造染色體結構﹑初始化種群，計算染色體的適應度﹑采取選擇﹑變異﹑交叉等操作，并不斷迭代搜索得到最優的染色體，即最優簇結構。得到最優簇結構的同時，也就得到了最優分布的簇頭。最后，各個簇頭向全網發送控制報文，選擇候選簇頭，創建低能量的簇。應用遺傳算法的關鍵操作有以下幾點。

（1）染色體編碼

采用01編碼的方式，即用一條染色體來表示一種分簇狀態，一個簇內的所有節點都位于該染色體上，區域內一個節點代表了該染色體中的一個基因位，簇頭節點和成員節點分別用1和0來編碼表示。

（2）建立適應度函數

適應度函數是衡量一個染色體能否正確優化的指標，決定著遺傳算法能否不斷向預設的優化目標有效趨近，即生成結構優化﹑能量消耗低的分簇結構。如何保證分簇均勻且總體耗能較低，是一個多目標優化問題。采用的各目標函數如下。

簇頭總距離（g1），表示某個簇頭的總距離等于簇內成員節點與簇頭節點之間的距離﹑簇頭和基站之間的距離之和。該值越小，則各個節點在數據傳輸時的相對距離最優。

能量消耗（g2），表示簇內信息報文傳輸到基站所消耗的能量。它包括成員節點將報文傳輸到簇頭節點和簇頭節點經過多跳將報文傳輸到基站所消耗的能量之和。該值越小，表示能量消耗越少。

無線傳感器網絡中，各分簇中成員節點數目的方差（g3）。該值越小，表明網絡分簇使得簇內節點數目越均勻，各簇首承擔的負載也相對均衡。

式（1）中，num表示節點總數目。式（2）中，TE(m)表示簇內第m個普通節點向簇頭傳輸報文的能量消耗，Mj表示第j個簇頭，Re表示簇頭接收報文能耗，TE1表示簇頭和基站之間的能耗。式（3）中，N表示節點總數目，p為最優簇頭數目的概率，通常為0.05；u表示網絡各分簇的非簇首子節點平均數。

設置適應度函數為：

其中a1+a2+a3=1。

對各個待優化的目標函數皆取對數，目的是為了使各個性能指標尺度能夠控制在同一個數量級上，避免某個性能指標過度影響整個遺傳優化的過程，導致某些優秀解被淘汰，陷入局部最優。

（3）遺傳操作

選擇操作。選擇操作是從當前群體中選出優良個體，使它們有機會作為父代繁殖下一代子孫。適應度值越高的染色體，表示使用該染色體所對應的簇狀態將會使得傳感器節點能量節省﹑延長網絡生命周期[9]，其被選中進行選擇操作的概率越大。本文使用賭輪選擇。

交叉操作。本文采用單點交叉，在兩條染色體中隨機產生一個交叉位置。如果一個普通節點通過交叉操作成為簇頭，所有其他的普通節點應該檢查它們是否接近該簇頭，以便判斷是否需要更新簇頭標記；若一個簇頭節點通過交叉操作成為了普通節點，它所有的成員必須查詢新的簇頭。

變異操作。在路徑中隨機選擇一個傳感器節點作為變異節點，對該傳感器節點變異概率pc=0.09進行基因的變異操作。

（4）終止條件

本文GA采取復合準則，設定最大進化代數和設定收斂條件。具體地，連續進化20代，最優解均未發生變化，且種群的平均適應度提高值不足1%就判定為收斂。

（5）具體算法流程

基于遺傳算法的無線傳感器網絡路由的基本流程如下：

①置群體代數gen=0，隨化產生規模M=100個個體的初始種群；

②計算群體中所有個體的適應度值，并根據結果按從小到大的順序排序；

③選取適應度高的個體，并對其進行遺傳操作產生下一代；

④檢驗結果是否為最優解或者gen=genmax，若是，則算法終止并輸出最優解；否則gen=gen+1，轉到②繼續操作。

3 基于跨層的簇間多跳選路策略

本文擬采用將MAC層與路由層相結合的方式進行整體設計來選擇簇間多跳的路由路徑，同時考慮MAC層協議如何避免節點間的碰撞和網絡層路由信息。

3.1 概念定義

能量標識符（El）：節點發送的路由包中帶有一個自身能量等級標志，共有三個等級，分別為normal﹑warning﹑danger。由式（5）可得出。

簇首節點偵聽狀態：簇首節點發射模塊打開狀態下，只要沒有數據發送，節點就一直處于偵聽信道狀態。

簇首節點數據發送狀態：簇首節點有新的大量數據需要發送至其他簇首節點或作為中繼節點轉發數據時，將會結束偵聽狀態。

中繼節點：能夠轉發其他簇頭節點發過來數據包的節點。規定能量等級為normal的節點才能擔當此功能。

隨機選擇標識符（RSD）：用來唯一標識節點名稱。

源梯度標識符（SGD）：由基站根據節點位置﹑節點與基站距離，經過特定公式計算得出的結果，并由基站廣播給節點。計算原則是距離基站越近的節點，其結果值越小，處于越低的梯度區間。

3.2 跨層多跳路由選擇機制

（1）當簇首有數據準備發送時，節點首先會等待一個時隙，稱為監聽時間，用t表示。在該期間，節點將會判斷信道是否為空閑狀態。

（2)若信道空閑，則進入隨機偵聽時間2t。若信道空閑，進入步驟（3）；如果信道忙，則節點一直偵聽信道，直到信道的空閑時間超過該間隔。當信道最終空閑下來時，節點使用二進制退避算法進入退避狀態避免發生碰撞。退避狀態下，只有當檢測到信道空閑時才進行計時。如果信道忙，退避計時器中止計時，直到檢測到信道空閑時間大于幀間間隔后才繼續計時。當多個節點推遲且進入隨機退避時，利用隨機函數選擇最小退避時間的節點作為競爭優勝者。

（3）節點發送一個請求中繼信號RT_R。此處，RT_R包含RSD與SGD。發送RT_R后，節點一直處于等待允許中繼信號（CT_R），并同時進入請求狀態。

（4）當位于低梯度的節點即下一跳節點接收到RT_R信號時，系統自動丟棄SGD比它小的節點，回復SGD比它大的節點。為避免與其他潛在的位于同一梯度的節點競爭，它在回復源節點前會等待一個隨機退避時間Tb，此期間則繼續偵聽信道。若在這個退避時間里，下一跳節點又偵聽到來自同一梯度的另一個下一跳節點的CT_R，且該CT_R包含了符合規定的RSD或是來自于源節點的數據，則說明存在其他傳輸在占用信道，節點返回至偵聽狀態。否則，退避時間超時后，該下一跳節點將發出含有SGD﹑RSD以及接收層標識符（RGD）的允許中繼信號CT_R。此時，它會等待源節點的數據，并進入接收狀態。

（5）一旦源節點成功接收到CT_R信號，它將馬上向下一跳節點發送數據。若下一跳節點接收到數據，則將向源節點發送ACK確認信號。通過該種方式，數據與確認在節點間形成快速交換，且使用了明確的中繼節點和源節點的標識符。為確保數據的無誤傳輸，在源節點和接收節點中設置了溢出時間Ta和Td，而下一跳節點成功接收數據幀后，將發送一個確認幀至發送節點。發送節點接收到該確認幀，說明發送成功。在規定時間內若未接收到確認幀，則將重發該數據幀。

（6）成功接收完數據后，更為靠近基站的下一跳節點則成為新的源節點，并將向更低梯度的節點請求數據的中繼轉發，并一直傳輸數據至基站。這樣就可以通過一個聯合設計的跨層方法解決接入與路由。

4 算法描述

（1）網絡初始化后按照遺傳算法將網絡區域分為面積大小不等的簇，同時選出每個簇的簇頭和候選簇頭。

（2）簇內普通節點按照TDMA的方式將數據發送給簇頭，簇頭根據跨層策略選擇到達目的節點的多跳路徑。

（3）基站根據傳來的數據包的能量字段計算，經過最終實驗驗證當，網絡中有1/3的節點能量為danger時，則重復（1）重新分簇，進行下一輪數據傳輸。此時，最能兼顧能量均衡和分簇輪數過多帶來的額外消耗。

5 仿真結果與分析

仿真工具采用EXata平臺，信道傳輸速率為2 Mb/s，信道傳輸范圍為250 m，無線電波干擾范圍為500 m。在100 m×100 m的矩形區域內，隨機分布100個無線節點，節點初始能量為1 J，每傳輸單位比時數據所消耗的能量Et=1 nJ。

確定最優簇頭數目采取LEACH協議中的計算方法，實驗中最優簇頭數目比率為0.05；交叉概率設定為0.6；兼顧質量和求解代價，取適應函數各權值為a1=a2=0.2﹑a3=6。表1是經過五輪后，LEACH協議和改進后的協議各簇頭剩余能量統計表。由表1可看出，改進后的協議各節點剩余能量更為均衡，變化量僅從0.49～0.70 J，而LEACH剩余能量不均，其分布范圍為0.20～0.91 J。因此，改進協議通過GA重新分簇達到了能量均衡的目的。

表1 剩余能量對比圖

圖1為網絡中死亡節點的個數隨仿真時間變化的情況。可以看出，在同一仿真時段，改進算法的節點能量耗盡數目明顯少于LEACH協議。原因是LEACH協議中遠離sink節點的簇頭節點通信距離太長，使得節點能量消耗速度加快，較早出現了能量耗盡。而改進算法采用簇間多跳，且多跳時避免選擇能量過低的節點，均衡了簇間能量消耗，優化了系統能量消耗。

圖1 節點生存時間對比圖

圖2為LEACH和改進算法每輪剩余能量。可知，由于改進算法應用了遺傳算法分簇，該過程消耗了一定能量，導致開始階段能量消耗過快。但是，改進算法使用了MAC層選路策略，能更好避免信道干擾，保證了鏈路質量，避免了數據包重發。此外，多跳策略能比LEACH更好地避免能量空洞。所以，經過3 000 s后，改進算法比LEACH多節約5%能量。

圖2 網絡剩余總能量對比圖

6 結 語

本文在LEACH路由協議基礎上，提出一種基于GA的分簇算法和跨層的簇間多跳路由算法。通過GA優化網絡拓撲結構，均衡了網絡能耗。通過將路由層和MAC層結合設計，采用簇間多跳方法，避免了能量空洞。仿真實驗結果表明，改進后的算法可以有效均衡網絡能量消耗，減少系統能量消耗，延長網絡生命周期。

[1] WANG Ying-guan,WANG Zhi.Wireless Sensor Network[M].Beijing:Publishing House of Electronics Industry,2012:2-3.

[2] Raman K K,Singh V.Transmission Energy Management for Wireless Sensor Network[C].2014 International Conference on Optimization,Reliabilty,and Information Technology(ICROIT),2014:245-248.

[3] Vazifehdan J,Prasad R V,Niemegeers I.Energy-Efficient Reliable Routing Considering Residual Energy in Wireless Ad Hoc Networks[J].IEEE Transactions on Mobile Computing,2014,13(02):434-447.

[4] Liao Q,Zhu H.An Energy Balanced Clustering Algorithm based on LEACH Protocol[J].Applied Mechanics&Materials,2013:341-342.

[5] H einzelman W B,Chandrakasan A P,Balakrishnan.An Application-specific Protocol Architecture for Wireless Micro Sensor Network[J].IEEE Transaction Wireless Communications,2000,1(04):1-10.

[6] Zuo J,Dong C,Ng S X,et al.Cross-Layer Aided Energy-Efficient Routing Design for Wireless Sensor Networks[J].IEEE Communications Surveys & Tutoria ls,2015,17(03):1214-1238.

[7] Ataul B,Shamsul W,Arunita,et al.A Genetic Algorithm Based Approach for Energy Efficient Routing in Two-tired Sensor Networks[J].Ad Hoc Networks,2009(07):665-676.

[8] Sanchez S M,Souza R D,Fernandez E M G,et al.Rate and Energy Efficient Power Control in a Cognitive Radio Ad Hoc Network[J].IEEE Signal Processing Letters,2013,20(05):451-454.

[9] Jin S,Zhou M,Wu A S.Sensor Network Optimization Using a Genetic Algorithm[C].7th World Multiconference on Systemic,Cyberbetics and Information,2003.