摘 要 糧庫WSN路由算法是WSN檢測糧庫糧食數量技術的難點之一。由于糧庫中傳感器節(jié)點分布的復雜性，所以其路由算法比較特殊。根據糧庫WSN的分布，提出一種RCCMA路由算法，先將大量分布不均的傳感器節(jié)點進行簇區(qū)域劃分和級別設定，然后利用最小夾角原則實現二級簇區(qū)域內節(jié)點間路由和一級簇區(qū)域與二級區(qū)域內目標節(jié)點間的路由。由于一級簇區(qū)域傳感器節(jié)點能耗較大，因此采用輪轉調度機制，將能耗平衡化，降低了單個傳感器節(jié)點的能耗。對比幾種典型的路由算法，實驗顯示，該算法具有明顯的優(yōu)勢。
關鍵詞 路由算法 簇區(qū)域 無線傳感器網絡
引 言
利用無線傳感器網絡檢測糧庫的糧食數量是一項新技術。由于糧堆的復雜性，可在糧庫底部散布大量分布不均的壓力傳感器節(jié)點。將糧庫內大量分布不均的傳感器節(jié)點進行組網，構建一種路由算法，這是糧庫WSN(Wire-less Sensor Network)的關鍵技術之一。
高效的路由算法需滿足以下幾點：能量高效(協議簡單和節(jié)省能量和均衡消耗)、可擴展性(網絡范圍和節(jié)點密度)、魯棒性(節(jié)點變化和拓撲變化)、快速收斂性。本文通過研究目前主要的幾種典型WSN路由算法，提出一種針對糧庫WSN的路由算法。實驗證明，該算法滿足能量高效性、可擴展性、魯棒性和快速收斂性要求。單個對比文中提到的幾種典型路由算法，該算法整體性能比它們都優(yōu)越。
1 典型的WSN路由算法
傳統(tǒng)無線通信網絡研究的重點放在無線通信的服務質量(QoS)上，而無線傳感器節(jié)點是隨機分布、電池供電的，因此無線傳感器網絡路由算法的研究重點放在如何提高能量效率上。目前典型的無線傳感器網絡路由算法主要有以下幾種。
1．1 泛洪算法
泛洪(Flooding)算法是一種傳統(tǒng)的無線通信路由算法。該算法規(guī)定，每個節(jié)點接收來自其他節(jié)點的信息，并以廣播的形式發(fā)送給其他鄰居節(jié)點。如此繼續(xù)下去，最后將信息數據發(fā)送給目的節(jié)點。但這個算法容易引起信息的“內爆”(implosion)和“重疊”(overlap)，造成資源的浪費。因此在泛洪算法的基礎上，提出了閑聊(Gossiping)算法。
1．2 Gossiping算法
Gossiping算法是在泛洪算法的基礎上進行改進而提出的。它傳播信息的途徑是，隨機地選擇一個鄰居節(jié)點，獲得信息的鄰居節(jié)點再以同樣的方式隨機地選擇下一個節(jié)點，進行信息的傳遞。這種方式避免了以廣播形式進行信息傳播的能量消耗，但其代價是延長了信息的傳遞時間。雖然Gossiping算法在一定程度上解決了信息的內爆問題，但是仍然存在信息的重疊現象。
1．3 SPIN算法
SPIN(Sensor Protocol for Information via Negotia-tion)算法是一種以數據為中心的自適應路由算法。其目的是通過節(jié)點之間的協商，解決Flooding算法和Gossi-ping算法的內爆和重疊問題。SPIN算法有3種類型的消息，即ADC、REQ和DATA。ADC用于數據的廣播，當某一個節(jié)點有數據可以共享時，可以用其進行數據信息廣播。REQ用于請求發(fā)送數據，當某一個節(jié)點希望接收DATA數據包時，發(fā)送REQ數據包。DATA為傳感器采集的數據包。在發(fā)送一個DATA數據包之前，一個傳感器節(jié)點首先對外廣播ADV數據包。如果某一個節(jié)點希望接收要傳來的數據信息，則向發(fā)送ADV數據包的節(jié)點回復REQ數據包，因此，便建立起發(fā)送節(jié)點和接收節(jié)點的聯系，發(fā)送節(jié)點便向接收節(jié)點發(fā)送DATA數據包。SPIN協議的工作流程如圖1所示。
1．4 定向擴散算法
定向擴散(Direeted Diffusion)算法是一種基于查詢的路由機制。整個過程可以分為興趣擴散、梯度建立以及路徑加強3個階段。在興趣擴散階段，匯聚節(jié)點向傳感器節(jié)點發(fā)送其想要獲取的信息種類或內容。興趣消息中含有任務類型、目標區(qū)域、數據發(fā)送速率、時間戳等參數。每個傳感器節(jié)點在收到該信息后，將其保存在Cache 中。當整個信息要求傳遍整個傳感器網絡后，便在傳感器節(jié)點和匯聚節(jié)點之間建立起一個梯度場，梯度場的建立是根據成本最小化和能量自適應原則。一旦傳感器節(jié)點收集到匯聚節(jié)點感興趣的數據，就會根據建立的梯度場尋求最快路徑進行數據傳遞。梯度場建立的過程如圖2所示。
1．5 LEACH算法
LEACH(LOW-Energy Adaptive Clustering Hier-archy)算法是一種以最小化傳感器網絡能量損耗為目標的分層式算法。該算法的主要思想是通過隨機選擇類頭節(jié)點，平均分擔無線傳感器網絡的中繼通信業(yè)務，以達到平均消耗傳感器網絡中節(jié)點能量的目的，進而延長網絡的生命周期。LEACH算法可以將網絡生命周期延長15％。LEACH算法分為兩個階段：類準備階段和數據傳輸階段。類準備階段和就緒階段所持續(xù)的時間總和稱為一個輪回。在類準備階段，LEACH算法隨機選擇一個傳感器節(jié)點作為類頭節(jié)點，隨機性確保類頭與基站之間數據傳輸的高能耗成本均勻地分攤到所有傳感器節(jié)點上。
2 RCCMA算法
定義1 簇區(qū)域，有一些相同的傳感器節(jié)點所占的區(qū)域，處在該區(qū)域內的節(jié)點功能相同。在本文中，一級簇區(qū)域內所有傳感器節(jié)點都具有輪轉調度機制、數據收發(fā)等功能，二級簇區(qū)域內傳感器節(jié)點不具有輪轉調度機制。
定義2 絕對夾角，不考慮方向，只考慮大小。
2．1 簇區(qū)域劃分和級別設定
如圖3所示，將糧庫底面區(qū)域化，在各個區(qū)域內計算傳感器節(jié)點密度，ρ=N／S。選取 3個密度最高的區(qū)域作為一級簇區(qū)域，其他區(qū)域為二級簇區(qū)域。在邊界線外部確定整個網絡的終極節(jié)點。設終極節(jié)點為O，選取的3個一級簇區(qū)域為A、B、C，終極節(jié)點到3個一級簇區(qū)域中心距離分別為dA、dB、dC，則終極節(jié)點位置滿足min{dA+dB+dC}。
2．2 二級簇區(qū)域內節(jié)點問路由
在二級簇區(qū)域內，選取一個到最近一級簇區(qū)域距離最短的節(jié)點作為該二級簇區(qū)域內的目標節(jié)點。利用最小夾角原則進行源節(jié)點到目標節(jié)點路由。具體步驟如下：
設節(jié)點1為該二級簇區(qū)域內選取的目標節(jié)點。節(jié)點8可向節(jié)點4通信，也可以向節(jié)點9通信。如果節(jié)點8、9都正常，則將節(jié)點8分別與節(jié)點4、節(jié)點9和節(jié)點1連接。以節(jié)點8與目標節(jié)點1的連線為終邊，以節(jié)點8與其相鄰的節(jié)點4、9連線為另一邊，判斷它們的絕對角大小。選取構成最小角的鄰節(jié)點作為源節(jié)點的下一跳路由節(jié)點，圖4中節(jié)點9構成的絕對夾角最小，故選擇節(jié)點9作為源節(jié)點8的下一跳路由節(jié)點。其他節(jié)點及其路由類似。
2．3 一級簇區(qū)域內節(jié)點問路由
一級簇區(qū)域負責與鄰近二級簇區(qū)域節(jié)點通信，同時負責與整個網絡終極節(jié)點通信，所以能耗最大。但是，一級簇區(qū)域內節(jié)點密度較高，采用輪轉調度機制，每個節(jié)點在某時承擔目標節(jié)點，將能耗平衡化，降低單個節(jié)點的能耗。
當某時該區(qū)域內某節(jié)點是目標節(jié)點時，該區(qū)域內的其他節(jié)點和其相鄰的二級簇區(qū)域內的目標節(jié)點都是該一級簇區(qū)域內目標節(jié)點的子節(jié)點。此時便是所有子節(jié)點與目標節(jié)點問的路由問題。同理，參照最小夾角原則進行路由規(guī)劃。
一級簇區(qū)域內目標節(jié)點匯聚了大量的數據，但節(jié)點數量較少(本例中任何時刻只有3個)。終極節(jié)點采用查詢機制與3個一級簇區(qū)域目標節(jié)點進行通信。
3 實驗結果
3．1 實驗環(huán)境
實驗采用30個能量相同的傳感器節(jié)點分別分布在10個等面積區(qū)域內，A、B、C三個區(qū)域節(jié)點密度最高，都布置了5個節(jié)點，其他區(qū)域節(jié)點布置如圖6所示。然后用一個終極節(jié)點和一級簇區(qū)域內節(jié)點通信，此終極節(jié)點能量和通信距離都比其他節(jié)點大。傳感器節(jié)點采用nRF905射頻芯片，ATmegal68單片機，供 3．3 V直流電(舊電池)。
3．2 實驗方法
①先按本路由算法實現整個WSN的通信，記錄最大通信延遲時間。然后，進行多次通信，消耗節(jié)點能量，直到網絡癱瘓，記錄網絡工作時間。最后，減少或增加傳感器節(jié)點，按本路由算法再次建立WSN路由，進行相同的測試。在多次測試中，記錄網絡出錯率。
②采用上述幾種典型的路由算法，按方法1進行同樣的測試。部分參數對比如表1所列。
實驗發(fā)現，本文提出的RCCMA路由算法在能量高效性、可擴展性、魯棒性和快速收斂性方面都比文中提到的幾種典型路由算法優(yōu)越。
4 結 論
本算法有效地把糧倉底部大量分布不均的傳感器節(jié)點進行了很好的路由，實現了整個網絡的通信路徑規(guī)劃。其創(chuàng)新點是先提出一種分級簇區(qū)域算法，將大量分布不均的傳感器節(jié)點進行了區(qū)域劃分和級別設定。然后提出一種基于最小夾角的路由算法，實現了二級簇區(qū)域內節(jié)點問路由和一級簇區(qū)域與二級區(qū)域內目標節(jié)點問的路由。由于一級簇區(qū)域負責與鄰近二級簇區(qū)域節(jié)點通信，同時負責與整個網絡終極節(jié)點通信，所以能耗最大。但是一級簇區(qū)域內節(jié)點密度較高，本文采用輪轉調度睡眠機制，每個節(jié)點在某時承擔目標節(jié)點，將能耗平衡化，降低了單個節(jié)點的能耗。
下載文檔
