作者：陳得民，張?jiān)?，賈德林，李鵬

引言

利用無(wú)線傳感器網(wǎng)絡(luò)檢測(cè)糧庫(kù)的糧食數(shù)量是一項(xiàng)新技術(shù)。由于糧堆的復(fù)雜性，可在糧庫(kù)底部散布大量分布不均的壓力傳感器節(jié)點(diǎn)。將糧庫(kù)內(nèi)大量分布不均的傳感器節(jié)點(diǎn)進(jìn)行組網(wǎng)，構(gòu)建一種路由算法，這是糧庫(kù)WSN（Wire-less Sensor Network）的關(guān)鍵技術(shù)之一。

高效的路由算法需滿足以下幾點(diǎn)：能量高效（協(xié)議簡(jiǎn)單和節(jié)省能量和均衡消耗）、可擴(kuò)展性（網(wǎng)絡(luò)范圍和節(jié)點(diǎn)密度）、魯棒性（節(jié)點(diǎn)變化和拓?fù)渥兓⒖焖偈諗啃?。本文通過(guò)研究目前主要的幾種典型WSN路由算法，提出一種針對(duì)糧庫(kù)WSN的路由算法。實(shí)驗(yàn)證明，該算法滿足能量高效性、可擴(kuò)展性、魯棒性和快速收斂性要求。單個(gè)對(duì)比文中提到的幾種典型路由算法，該算法整體性能比它們都優(yōu)越。

1 典型的WSN路由算法

傳統(tǒng)無(wú)線通信網(wǎng)絡(luò)研究的重點(diǎn)放在無(wú)線通信的服務(wù)質(zhì)量（QoS）上，而無(wú)線傳感器節(jié)點(diǎn)是隨機(jī)分布、電池供電的，因此無(wú)線傳感器網(wǎng)絡(luò)路由算法的研究重點(diǎn)放在如何提高能量效率上。目前典型的無(wú)線傳感器網(wǎng)絡(luò)路由算法主要有以下幾種。

1．1 泛洪算法

泛洪（Flooding）算法是一種傳統(tǒng)的無(wú)線通信路由算法。該算法規(guī)定，每個(gè)節(jié)點(diǎn)接收來(lái)自其他節(jié)點(diǎn)的信息，并以廣播的形式發(fā)送給其他鄰居節(jié)點(diǎn)。如此繼續(xù)下去，最后將信息數(shù)據(jù)發(fā)送給目的節(jié)點(diǎn)。但這個(gè)算法容易引起信息的“內(nèi)爆”（implosion）和“重疊”（overlap），造成資源的浪費(fèi)。因此在泛洪算法的基礎(chǔ)上，提出了閑聊（Gossiping）算法。

1．2 Gossiping算法

Gossiping算法是在泛洪算法的基礎(chǔ)上進(jìn)行改進(jìn)而提出的。它傳播信息的途徑是，隨機(jī)地選擇一個(gè)鄰居節(jié)點(diǎn)，獲得信息的鄰居節(jié)點(diǎn)再以同樣的方式隨機(jī)地選擇下一個(gè)節(jié)點(diǎn)，進(jìn)行信息的傳遞。這種方式避免了以廣播形式進(jìn)行信息傳播的能量消耗，但其代價(jià)是延長(zhǎng)了信息的傳遞時(shí)間。雖然Gossiping算法在一定程度上解決了信息的內(nèi)爆問(wèn)題，但是仍然存在信息的重疊現(xiàn)象。

1．3 SPIN算法

SPIN（Sensor Protocol for Information via Negotia-tion）算法是一種以數(shù)據(jù)為中心的自適應(yīng)路由算法。其目的是通過(guò)節(jié)點(diǎn)之間的協(xié)商，解決Flooding算法和Gossi-ping算法的內(nèi)爆和重疊問(wèn)題。SPIN算法有3種類型的消息，即ADC、REQ和DATA。ADC用于數(shù)據(jù)的廣播，當(dāng)某一個(gè)節(jié)點(diǎn)有數(shù)據(jù)可以共享時(shí)，可以用其進(jìn)行數(shù)據(jù)信息廣播。REQ用于請(qǐng)求發(fā)送數(shù)據(jù)，當(dāng)某一個(gè)節(jié)點(diǎn)希望接收DATA數(shù)據(jù)包時(shí)，發(fā)送REQ數(shù)據(jù)包。DATA為傳感器采集的數(shù)據(jù)包。在發(fā)送一個(gè)DATA數(shù)據(jù)包之前，一個(gè)傳感器節(jié)點(diǎn)首先對(duì)外廣播ADV數(shù)據(jù)包。如果某一個(gè)節(jié)點(diǎn)希望接收要傳來(lái)的數(shù)據(jù)信息，則向發(fā)送ADV數(shù)據(jù)包的節(jié)點(diǎn)回復(fù)REQ數(shù)據(jù)包，因此，便建立起發(fā)送節(jié)點(diǎn)和接收節(jié)點(diǎn)的聯(lián)系，發(fā)送節(jié)點(diǎn)便向接收節(jié)點(diǎn)發(fā)送DATA數(shù)據(jù)包。SPIN協(xié)議的工作流程如圖1所示。

1．4 定向擴(kuò)散算法

定向擴(kuò)散（Direeted Diffusion）算法是一種基于查詢的路由機(jī)制。整個(gè)過(guò)程可以分為興趣擴(kuò)散、梯度建立以及路徑加強(qiáng)3個(gè)階段。在興趣擴(kuò)散階段，匯聚節(jié)點(diǎn)向傳感器節(jié)點(diǎn)發(fā)送其想要獲取的信息種類或內(nèi)容。興趣消息中含有任務(wù)類型、目標(biāo)區(qū)域、數(shù)據(jù)發(fā)送速率、時(shí)間戳等參數(shù)。每個(gè)傳感器節(jié)點(diǎn)在收到該信息后，將其保存在Cache 中。當(dāng)整個(gè)信息要求傳遍整個(gè)傳感器網(wǎng)絡(luò)后，便在傳感器節(jié)點(diǎn)和匯聚節(jié)點(diǎn)之間建立起一個(gè)梯度場(chǎng)，梯度場(chǎng)的建立是根據(jù)成本最小化和能量自適應(yīng)原則。一旦傳感器節(jié)點(diǎn)收集到匯聚節(jié)點(diǎn)感興趣的數(shù)據(jù)，就會(huì)根據(jù)建立的梯度場(chǎng)尋求最快路徑進(jìn)行數(shù)據(jù)傳遞。梯度場(chǎng)建立的過(guò)程如圖2所示。

1．5 LEACH算法

LEACH（LOW-Energy Adaptive Clustering Hier-archy）算法是一種以最小化傳感器網(wǎng)絡(luò)能量損耗為目標(biāo)的分層式算法。該算法的主要思想是通過(guò)隨機(jī)選擇類頭節(jié)點(diǎn)，平均分擔(dān)無(wú)線傳感器網(wǎng)絡(luò)的中繼通信業(yè)務(wù)，以達(dá)到平均消耗傳感器網(wǎng)絡(luò)中節(jié)點(diǎn)能量的目的，進(jìn)而延長(zhǎng)網(wǎng)絡(luò)的生命周期。LEACH算法可以將網(wǎng)絡(luò)生命周期延長(zhǎng)15％。LEACH算法分為兩個(gè)階段：類準(zhǔn)備階段和數(shù)據(jù)傳輸階段。類準(zhǔn)備階段和就緒階段所持續(xù)的時(shí)間總和稱為一個(gè)輪回。在類準(zhǔn)備階段，LEACH算法隨機(jī)選擇一個(gè)傳感器節(jié)點(diǎn)作為類頭節(jié)點(diǎn)，隨機(jī)性確保類頭與基站之間數(shù)據(jù)傳輸?shù)母吣芎某杀揪鶆虻胤謹(jǐn)偟剿袀鞲衅鞴?jié)點(diǎn)上。

2 RCCMA算法

定義1 簇區(qū)域，有一些相同的傳感器節(jié)點(diǎn)所占的區(qū)域，處在該區(qū)域內(nèi)的節(jié)點(diǎn)功能相同。在本文中，一級(jí)簇區(qū)域內(nèi)所有傳感器節(jié)點(diǎn)都具有輪轉(zhuǎn)調(diào)度機(jī)制、數(shù)據(jù)收發(fā)等功能，二級(jí)簇區(qū)域內(nèi)傳感器節(jié)點(diǎn)不具有輪轉(zhuǎn)調(diào)度機(jī)制。

定義2 絕對(duì)夾角，不考慮方向，只考慮大小。

2．1 簇區(qū)域劃分和級(jí)別設(shè)定

如圖3所示，將糧庫(kù)底面區(qū)域化，在各個(gè)區(qū)域內(nèi)計(jì)算傳感器節(jié)點(diǎn)密度，ρ=N／S。選取 3個(gè)密度最高的區(qū)域作為一級(jí)簇區(qū)域，其他區(qū)域?yàn)槎?jí)簇區(qū)域。在邊界線外部確定整個(gè)網(wǎng)絡(luò)的終極節(jié)點(diǎn)。設(shè)終極節(jié)點(diǎn)為O，選取的3個(gè)一級(jí)簇區(qū)域?yàn)锳、B、C，終極節(jié)點(diǎn)到3個(gè)一級(jí)簇區(qū)域中心距離分別為dA、dB、dC，則終極節(jié)點(diǎn)位置滿足min{dA+dB+dC}。

2．2 二級(jí)簇區(qū)域內(nèi)節(jié)點(diǎn)問(wèn)路由

在二級(jí)簇區(qū)域內(nèi)，選取一個(gè)到最近一級(jí)簇區(qū)域距離最短的節(jié)點(diǎn)作為該二級(jí)簇區(qū)域內(nèi)的目標(biāo)節(jié)點(diǎn)。利用最小夾角原則進(jìn)行源節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)路由。具體步驟如下：

設(shè)節(jié)點(diǎn)1為該二級(jí)簇區(qū)域內(nèi)選取的目標(biāo)節(jié)點(diǎn)。節(jié)點(diǎn)8可向節(jié)點(diǎn)4通信，也可以向節(jié)點(diǎn)9通信。如果節(jié)點(diǎn)8、9都正常，則將節(jié)點(diǎn)8分別與節(jié)點(diǎn)4、節(jié)點(diǎn)9和節(jié)點(diǎn)1連接。以節(jié)點(diǎn)8與目標(biāo)節(jié)點(diǎn)1的連線為終邊，以節(jié)點(diǎn)8與其相鄰的節(jié)點(diǎn)4、9連線為另一邊，判斷它們的絕對(duì)角大小。選取構(gòu)成最小角的鄰節(jié)點(diǎn)作為源節(jié)點(diǎn)的下一跳路由節(jié)點(diǎn)，圖4中節(jié)點(diǎn)9構(gòu)成的絕對(duì)夾角最小，故選擇節(jié)點(diǎn)9作為源節(jié)點(diǎn)8的下一跳路由節(jié)點(diǎn)。其他節(jié)點(diǎn)及其路由類似。

2．3 一級(jí)簇區(qū)域內(nèi)節(jié)點(diǎn)問(wèn)路由

一級(jí)簇區(qū)域負(fù)責(zé)與鄰近二級(jí)簇區(qū)域節(jié)點(diǎn)通信，同時(shí)負(fù)責(zé)與整個(gè)網(wǎng)絡(luò)終極節(jié)點(diǎn)通信，所以能耗最大。但是，一級(jí)簇區(qū)域內(nèi)節(jié)點(diǎn)密度較高，采用輪轉(zhuǎn)調(diào)度機(jī)制，每個(gè)節(jié)點(diǎn)在某時(shí)承擔(dān)目標(biāo)節(jié)點(diǎn)，將能耗平衡化，降低單個(gè)節(jié)點(diǎn)的能耗。

當(dāng)某時(shí)該區(qū)域內(nèi)某節(jié)點(diǎn)是目標(biāo)節(jié)點(diǎn)時(shí)，該區(qū)域內(nèi)的其他節(jié)點(diǎn)和其相鄰的二級(jí)簇區(qū)域內(nèi)的目標(biāo)節(jié)點(diǎn)都是該一級(jí)簇區(qū)域內(nèi)目標(biāo)節(jié)點(diǎn)的子節(jié)點(diǎn)。此時(shí)便是所有子節(jié)點(diǎn)與目標(biāo)節(jié)點(diǎn)問(wèn)的路由問(wèn)題。同理，參照最小夾角原則進(jìn)行路由規(guī)劃。

一級(jí)簇區(qū)域內(nèi)目標(biāo)節(jié)點(diǎn)匯聚了大量的數(shù)據(jù)，但節(jié)點(diǎn)數(shù)量較少（本例中任何時(shí)刻只有3個(gè)）。終極節(jié)點(diǎn)采用查詢機(jī)制與3個(gè)一級(jí)簇區(qū)域目標(biāo)節(jié)點(diǎn)進(jìn)行通信。

3 實(shí)驗(yàn)結(jié)果

3．1 實(shí)驗(yàn)環(huán)境

實(shí)驗(yàn)采用30個(gè)能量相同的傳感器節(jié)點(diǎn)分別分布在10個(gè)等面積區(qū)域內(nèi)，A、B、C三個(gè)區(qū)域節(jié)點(diǎn)密度最高，都布置了5個(gè)節(jié)點(diǎn)，其他區(qū)域節(jié)點(diǎn)布置如圖6所示。然后用一個(gè)終極節(jié)點(diǎn)和一級(jí)簇區(qū)域內(nèi)節(jié)點(diǎn)通信，此終極節(jié)點(diǎn)能量和通信距離都比其他節(jié)點(diǎn)大。傳感器節(jié)點(diǎn)采用nRF905射頻芯片，ATmegal68單片機(jī)，供 3．3 V直流電（舊電池）。

3．2 實(shí)驗(yàn)方法

①先按本路由算法實(shí)現(xiàn)整個(gè)WSN的通信，記錄最大通信延遲時(shí)間。然后，進(jìn)行多次通信，消耗節(jié)點(diǎn)能量，直到網(wǎng)絡(luò)癱瘓，記錄網(wǎng)絡(luò)工作時(shí)間。最后，減少或增加傳感器節(jié)點(diǎn)，按本路由算法再次建立WSN路由，進(jìn)行相同的測(cè)試。在多次測(cè)試中，記錄網(wǎng)絡(luò)出錯(cuò)率。

②采用上述幾種典型的路由算法，按方法1進(jìn)行同樣的測(cè)試。部分參數(shù)對(duì)比如表1所列。

實(shí)驗(yàn)發(fā)現(xiàn)，本文提出的RCCMA路由算法在能量高效性、可擴(kuò)展性、魯棒性和快速收斂性方面都比文中提到的幾種典型路由算法優(yōu)越。

4 結(jié)論

本算法有效地把糧倉(cāng)底部大量分布不均的傳感器節(jié)點(diǎn)進(jìn)行了很好的路由，實(shí)現(xiàn)了整個(gè)網(wǎng)絡(luò)的通信路徑規(guī)劃。其創(chuàng)新點(diǎn)是先提出一種分級(jí)簇區(qū)域算法，將大量分布不均的傳感器節(jié)點(diǎn)進(jìn)行了區(qū)域劃分和級(jí)別設(shè)定。然后提出一種基于最小夾角的路由算法，實(shí)現(xiàn)了二級(jí)簇區(qū)域內(nèi)節(jié)點(diǎn)問(wèn)路由和一級(jí)簇區(qū)域與二級(jí)區(qū)域內(nèi)目標(biāo)節(jié)點(diǎn)問(wèn)的路由。由于一級(jí)簇區(qū)域負(fù)責(zé)與鄰近二級(jí)簇區(qū)域節(jié)點(diǎn)通信，同時(shí)負(fù)責(zé)與整個(gè)網(wǎng)絡(luò)終極節(jié)點(diǎn)通信，所以能耗最大。但是一級(jí)簇區(qū)域內(nèi)節(jié)點(diǎn)密度較高，本文采用輪轉(zhuǎn)調(diào)度睡眠機(jī)制，每個(gè)節(jié)點(diǎn)在某時(shí)承擔(dān)目標(biāo)節(jié)點(diǎn)，將能耗平衡化，降低了單個(gè)節(jié)點(diǎn)的能耗。

責(zé)任編輯：gt