定向天線WSN改進算法RADA的設計與實現

◆鄭少雄

（廣東生態工程職業學院 廣東 510642）

定向天線WSN改進算法RADA的設計與實現

◆鄭少雄

（廣東生態工程職業學院 廣東 510642）

傳統的無線傳感器網絡LEACH算法由于在簇頭形成時沒有考慮節點的能量和位置，存在著網絡能耗過大的缺點，本文利用定向天線能夠對射頻信號進行定向擴散的特點，對獨立節點進行分簇歸類，設計改進路由算法，并在NS2網絡模擬軟件平臺上進行仿真，對改進的算法與LEACH算法進行對比分析，結果表明RADA算法使得網絡的生命周期更加延長，網絡穩定性更好。

無線傳感器網絡; RADA; 路由算法

0 前言

無線傳感器網絡（WSN，Wireless Sensor Network）是一門新興的科學技術，具有無線感知、監測和控制等功能，也具有成本低、微型化、實時監測、可嵌入等優點，已經得到廣泛的應用。本文設計了一種基于定向天線的WSN匯聚節點控制路由算法，該算法通過對WSN節點進行分簇迭代，利用定向天線射頻信號定向擴散的特點，對獨立節點進行分簇歸類，使單獨節點進入距離自己最近的簇群，減少了網絡簇頭形成過程中選擇的隨機性。采用步進電機驅動定向天線轉動，讓定向天線WSN匯聚節點能夠收集到不同方位的簇頭發送來的數據。該算法能夠明顯降低Leach算法中孤立節點的數目，使其無須參加簇間路由查找，節省了網絡節點能量的消耗。

1 RADA算法

1.1 RADA算法的介紹

定向天線WSN匯聚節點控制路由算法（RADA，WSN aggregation node control routing algorithm based on Directional antenna）最重要的特點就是在無線傳感器網絡的匯聚節點中利用了定向天線。由于在定向天線WSN匯聚節點的信號覆蓋范圍內，成員節點能夠把遠處收集到的監測信號通過通信鏈路傳送給簇頭。在數據接收方面，定向天線WSN匯聚節點采用步進電機來驅動定向天線的轉動，根據設定的轉動周期，實現對定向天線WSN簇頭節點的信號覆蓋區域監測數據的收集。在定向天線WSN匯聚節點控制路由算法中，能夠收集到各個扇形區域內成員節點環境信息的節點成為簇頭。這里并非所有的簇頭都直接和匯聚節點進行通信，而是根據節點自身與匯聚節點的距離情況決定自身能否成為低一級簇頭，只有與匯聚節點在天線的通信范圍內才直接和定向天線WSN匯聚節點進行通信。當一個簇頭的成員中具有一級簇頭的時候，則自身默認成為二級簇頭。在定向天線WSN匯聚節點控制路由算法中，簇頭節點根據自身能量的剩余情況進行輪換，當具有相同覆蓋程度的節點能量下降到一定程度以后，簇頭向覆蓋程度低一級別的節點進行輪換。

1.2 RADA算法網絡初始化

在基于定向天線的WSN中，將定向天線配置在WSN匯聚節點上，而用全向天線配置在其他成員節點上。在網絡初始化的時候，所有節點已經得知匯聚節點的位置。由圖1所示，匯聚節點位于網絡邊緣的正下方，匯聚節點以α角度為輻射角向成員節點方向發出廣播信號，此時WSN匯聚節點的天線信號輻射范圍為直徑d。

由圖1可以看到，網絡覆蓋區域中灰色節點成為覆蓋它所在區域白色節點的簇頭（一級簇頭）。但是，有時候也會存在一級簇頭的監測區域中節點的被覆蓋程度較低，沒有節點會被挑選為簇頭。這些節點和一級簇頭都采用相同的模式向匯聚節點信號的輻射方向定向地發出廣播信號。根據信號覆蓋程度，在離匯聚節點較近的范圍內選出新的簇頭，在這類簇頭中，如果成員節點有一級簇頭的，則自身會成為二級簇頭，如圖1中所示黑色節點。當成員節點中不存在一級簇頭，則將自身定位為一級簇頭。這樣網絡從由遠離定向天線WSN匯聚節點的區域到靠近定向天線WSN匯聚節點的區域一層一層地形成簇群，以及相應不同級別的簇頭。當節點的發射信號層層覆蓋到定向天線WSN匯聚節點后，簇群的形成進入穩定階段。

圖1 定向天線WSN簇頭更替流程圖

1.3 RADA網絡穩定階段

當網絡初始化完成，簇群的分布穩定以后，每個簇內部成員節點開始進行相應的信息收集，并且把收集到的信息定期或者在定向天線WSN匯聚節點的查詢要求下把信息數據發送到簇頭。一級簇頭和LEACH算法中的簇頭一樣，可以向成員節點發送來自定向天線WSN匯聚節點的查詢信息。簇頭節點在接收到簇內成員節點的信息后，則對數據進行壓縮融合，當數據不能直接傳送給簇內匯聚節點時候，則轉發給二級簇頭或者定向天線WSN匯聚節點。一級簇頭向二級簇頭發送信息時候在數據包加入一定的標識，以便二級簇頭選取。

圖2 網絡穩定階段數據流程圖

同樣，二級簇頭有也具備一級簇頭的功能，能自身通過辨認而獲得來自一級簇頭的數據包，而不對此數據包做壓縮和融合處理。這樣不僅能夠減小二級簇頭的處理負載程度，而且能夠減少二次壓縮所到來的數據丟失的風險。在WSN大面積監測的應用情況下，WSN則可能出現三級或者以上的簇頭。更高一級的簇頭和二級簇頭的工作原理相類似。圖2是利用定向天線WSN匯聚節點控制路由算法的WSN網絡穩定階段的數據流程圖。

1.4 RADA算法的簇頭輪換策略

當定向天線WSN網絡完成初始化并運行一段時間后，充當簇頭節點的能量會下降到較低等級，此時如果繼續充當簇頭節點，則簇頭節點會很快進入死亡狀態，使得網絡不能正常工作。因此算法中所設定的簇頭能量下降為原來的1/2時候，網絡重新輪換簇頭。

RADA算法簇頭輪換方式有以下兩種，第一種輪換條件是在具有相同被覆蓋程度時候進行，另外一種輪換情況是在具有不同被覆蓋程度時候進行。而無論哪種情況下的簇頭，只要能量下降到原來的1/2時候，則開始尋找能夠替代該簇頭功能的鄰節點。當WSN網絡在判斷靠近簇頭區域內沒有存在被匯聚節點覆蓋程度相同的鄰節點時，由圖1能夠看到中間2個灰色的節點被相同的成員節點所覆蓋。當滿足這種條件時候，則將鄰居節點輪換為簇頭，把信號發送至原來的子節點，并通知其他成員節點將數據發送給新的簇頭。

而靠近原簇頭較近距離范圍內沒存在與鄰節點相同覆蓋程度時，網絡會重新初始化并繼續尋找覆蓋程度低于原簇頭的鄰節點，并把該鄰節點更換為新簇頭。新簇頭會覆蓋新的簇群，完成一次簇頭輪換后，網絡就會進入下一次穩定的運行階段。第二次輪換是在第一次輪換的基礎上進行，新簇頭節點的覆蓋程度較原簇頭節點的覆蓋程度低。當WSN網絡中節點密度分布較高時候，那么網絡區域中有10%的節點被簇頭射頻輻射信號所覆蓋，而當網絡中節點的分布密度較低時候，網絡區域中有20%的節點被簇頭射頻信號所覆蓋。圖3是定向天線WSN匯聚節點路由控制算法中簇頭輪換策略的流程圖：

圖3 定向天線WSN匯聚節點路由控制算法中簇頭的輪換策略

由上圖可見，當WSN網絡經過多次的簇頭輪換后沒能找到可以正常工作的簇頭時，說明WSN節點的能耗過低，不能支持網絡的正常運行，需要重新進行初始化。由于WSN節點數目較多，當部分簇頭節點能量減少為原來的1/2時候。網絡重新進行初始化，能量等級進行重新定義，最終形成新的網絡簇群。

2 RADA算法的仿真分析

2.1 簇頭數目比較

上文提到，WSN網絡中簇頭競爭半徑的大小直接和網絡的拓撲結構和簇的密度有關。由公式

可以看出，簇頭的競爭半徑除了由網絡中的硬件環境決定外，還由控制參數c以及競爭半徑CR共同決定，因此網絡中簇頭數目受節點的最大發射半徑以及控制參數c的影響。

圖4 RADA生成的簇頭數目與控制參數間的關系

圖4為對RADA路由算法生成的簇頭數目與控制參數間的關系進行仿真而得到的曲線圖，由圖4可以看到，在控制參數c不變的情況下，隨著競爭半徑CR的增大，網絡中總的簇頭節點數目的下降速度明顯較快。在競爭半徑CR不變的情況下，c =0時候相當于各簇頭均以最大競爭半徑分簇，由于要覆蓋網絡中的全部節點，c =0.5時候網絡的簇頭數要多于c =0時候網絡的簇頭數也屬必然。

圖5 RADA簇頭分布數目

從圖5可以看出RADA算法的簇頭的數目較為集中，因為該算法采用了非隨機算法在局部區域進行競爭，從而控制了算法生成簇頭的數目。加上算法針對孤立簇頭節點采用根據距離選擇入簇，或是直接與匯聚節點通信的方式，降低了整個簇頭數目的差異性，使整個簇比較穩定地分布在一個相對較小的范圍內。仿真后的RADA路由算法與LEACH算法相比具有更為優化的試驗結果。

由圖5可以看到，簇頭數目較少的情況出現的次數較多，表明簇頭數目確實有明顯的下降現象。由于簇頭節點數目減少，使得網絡中簇頭數目的分布有下降趨勢。同時也保證了網絡良好的穩定性和連通性，為后續簇頭間的輪換通信打下了可靠的基礎。

2.2 每輪簇頭能耗總和比較

網絡的能耗仿真過程主要針對簇頭的能量消耗情況進行，是由于簇頭的能耗在整個網絡中所占的比重較大。圖6是對隨機挑選的簇頭進行10輪迭代分簇后，對簇頭節點能量消耗的總和進行對比的仿真圖。

圖6 RADA算法每輪簇頭能耗總和

從圖6可以看出，RADA算法比LEACH算法在每輪簇頭總能耗上有較好的試驗結果，具有較低的能耗總和。RADA算法能夠有效處理孤立簇頭節點產生的能耗問題，使得簇頭數目相對減少。由于降低了分簇階段簇頭的總能耗，能量相應存留在需要能耗更大的簇間通信上，如匯聚節點通信、路由建立、尋路轉發等方面的能耗上。

2.3 網絡生存時間比較

通過網絡仿真，得出RADA 算法和LEACH算法在整個網絡存活時間上的差異。圖7顯示了隨著時間的增長，RADA 算法和LEACH算法在網絡存活時間里簇頭節點數量的變化。通過存活簇頭節點的數目變化，能夠客觀反映整個網絡生存周期的長短。