改進的分簇路由協議方案ADEECS - 全文

　　1 引言

　　無線傳感器網絡(Wireless Sensor Network，WSN)是由大量具有特定功能的傳感器節點通過自組織的無線通信方式，相互傳遞信息，協同地完成特定功能的智能專用網絡。傳感器網絡一般投放在條件惡劣的環境或者難以涉足的地域中，節點電池的更換或能量的補充幾乎是不可能的，所以節能路由協議的設計，對無線傳感器網絡來說意義十分重大。目前，提出的WSN路由協議主要有平面路由協議和層次路由協議兩類，其中基于簇結構的層次路由協議是當前國內外研究的熱點口。

　　1相關研究

　　WSN分簇路由協議設計的首要目標是通過高效的分簇算法形成合理的網絡結構，通過主動的能量管理阻止網絡連通性下降，延長網絡的生命周期。最典型的無線傳感器網絡分簇路由協議是LEACH協議，人們在LEACH協議的基礎上也研究出很多改進的分簇路由協議，EECS(Energy Efficient Clustering Scheme)協議就是其中一種經典的改進算法。

　　1.1LEACH協議

　　LEACH是分布式成簇協議的代表。每個節點產生一個0～1的隨機數，如果這個數小于閾值，則該節點向整個網絡廣播它是簇頭。閾值的計算公式為：

　　式中：p是簇頭占所有節點的百分比，即節點當選為簇頭的初始概率，實際的簇頭概率以p為中心上下浮動;r是目前循環進行的輪;G是在最近1/p輪中沒有當選過簇頭的節點集合。可以看出，當選過簇頭的節點在接下來的1輪中將不能成為簇頭，而其他節點，因節點產生小于T(n)隨機數的概率隨之增大，所以節點當選為簇頭的概率也增大。競爭成功的簇頭節點廣播當選的消息后，其他節點根據簇頭廣播信號的強弱決定加入哪個簇。由于簇頭是隨機挑選的，因此LEACH協議不能保證簇頭在網絡中分布均勻，而且節點根據自身通信代價最小原則選擇加入哪個簇的成簇算法，但不能保證簇的負載均衡。

　　1.2 EECS協議

　　如前所述，LEACH等算法中，節點根據自身通信代價最小原則選擇加入哪個簇，不能保證簇的負載平衡，而且沒有考慮距基站較遠的簇頭能量耗費過快等問題。針對這些問題，EECS提出一個新的通信代價公式(2)來決定節點加入哪個簇：

　　式中：cost(j，i)是節點Pj加入簇頭i的代價;d(Pj，CHi)是節點到簇頭的距離。式(3)中f子函數保證最小化節點與簇頭之間的通信代價;d(CHi，BS)是簇頭i到基站的距離，式(3)中g子函數保證最小化簇頭i到基站的通信代價;權值w的設置則根據具體應用，在成員節點能量與簇頭能量消耗之間折衷，目標是最大化網絡生命周期。節點Pj選擇cost(j，i)最小的簇頭i加入，從而保證每個簇頭負載均衡。實驗結果顯示，EECS協議的網絡生命周期較LEACH協議提高了30%以上。

　　2問題的描述

　　EECS算法的實質是在簇頭選擇階段，總是讓剩余能量最大的節點當選為簇頭;在成簇階段，聯合考慮普通節點與簇頭的距離，以及簇頭與基站的距離。其創新之處在于：只有小部分節點參加簇頭的競選;在局部范圍內廣播消息，選舉過程沒有迭代;以節點的剩余能量為競選參數;設計了簇頭之間負載均衡的策略。

　　EECS協議存在的問題：

　　(1)EECS算法在成簇階段讓候選節點同時廣播競選消息COMPETE_HEAD，容易造成簇頭分布漏洞問題。如圖1所示，節點C在B的競選半徑內;節點B在A的競選半徑內，且剩余能量方面A>B>C。在這種情況下，C收到B的競選消息退出競選的同時，B收到A的競選消息退出競選，這就會造成局部簇頭分布漏洞的情況。

　　(2)EECS算法在成簇階段的通信代價只考慮了普通節點與簇頭的距離，以及簇頭與基站的距離，沒有考慮簇頭的剩余能量。這樣就會造成部分剩余能量相對較少簇頭節點的早死現象。

　　針對EECS協議存在的問題提出了ADEECS(Advanced EECS)協議，該算法在簇頭選舉階段使用了競爭延遲的方法，在成簇階段設計了新的通信代價計算公式。

　　3 ADEECS路由協議

　　方案中，假設已知發送節點的發射功率，接收節點可以根據接收信號的強度，計算二者之間距離的近似值;發射功率可控，即節點可以根據自身需要調整發射功率。采用與文獻[5]相同的無線傳輸能量消耗模型。ADEECS協議按輪執行，每一輪分為網絡部署，簇頭選舉，成簇，數據傳輸這4個階段。

　　具體實現過程如下：

　　階段1：網絡部署階段在網絡部署階段，讓基站以一定的功率向網絡內廣播一個消息HELLO_MSG。傳感器節點根據接收信號的強度計算出自己到基站的近似距離，在與基站通信時，依據這個距離選擇適當的發射功率。在成簇階段，還將利用這個信息來均衡簇頭的負載。

　　階段2：簇頭選舉階段全局范圍內預先設定一個0～1之間的閾值T，用來控制參加簇頭競選的節點比例。每一個節點生成一個0～1之間的隨機數，記為u。若u

　　式中：T為最大約定的最大延遲時間;Eresidual為節點剩余能量;Eini是節點原始能量。

　　階段3：成簇階段簇頭向網絡所有節點廣播自己成為簇頭的消息HEAD_AD，內容為簇頭節點的標識及該節點與基站的距離。普通節點接收到此消息后選擇一個通信代價cost(CH)最小的聚類加入，并發送消息JOIN_REQ。通信代價表達式為：

　　式(5)中參數與式(2)和式(4)表示的意義相同。從式(5)可以看出，該通信代價綜合考慮了節點與簇頭的距離、簇頭與基站的距離及簇頭的剩余能量。從而實現了由聚類成員節點選擇剩余能量較大，與自己距離較近，與基站距離較小的簇頭形成簇，達到能量均衡的目的。

　　階段4：數據傳輸階段簇頭向所有成員節點廣播TDMA通信時隙調度信息TDMA_SCHEDULE。成員節點按分配好的TDMA時隙在某個時刻將自己檢測到的數據發送給簇頭。簇頭在接收聚類成員發送數據的過程中進行數據融合，并將融合后的數據直接傳輸給基站，該過程采用單跳的通信方式。

　　4 ADEECS協議仿真與分析

　　仿真中，使用Matlab作為仿真平臺，采用與文獻[3]相同的能量消耗模型。仿真參數如表1所示。

　　文中將ADEECS與EECS和LEACH協議性能進行仿真對比。

　　4.1簇頭分布的仿真對比

　　LEACH簇頭個數取最優值。在仿真中，LEACH簇頭個數為6;取T=0.15，R=26，w=0.8。由3種協議的簇頭分布圖(圖2～圖4)可以看出，LEACH協議簇頭隨機分布;EECS協議簇頭分布比較均勻，但存在簇頭漏洞問題;ADEECS協議簇頭真正實現了均勻分布。所以，提出的延遲發送競選消息的方法很好地解決了LEACH和EECS協議在簇頭選舉過程中存在的問題。