李峰+李世偉

摘 要：針對大型建筑物內(nèi)部無線自組網(wǎng)組網(wǎng)算法存在數(shù)據(jù)采集不全、采集周期長等缺陷，提出了多障礙環(huán)境下基于RSSI的低速組網(wǎng)算法。為保證數(shù)據(jù)的可達(dá)性，該算法以實際節(jié)點連通狀態(tài)進(jìn)行定位并構(gòu)建虛擬網(wǎng)絡(luò)，節(jié)點間通過相互探測的方式進(jìn)行路由選擇，以節(jié)點接收的RSSI和節(jié)點間的實際通信距離作為選擇依據(jù)。通過該算法，可以有效提高大型建筑物內(nèi)部自組網(wǎng)數(shù)據(jù)的可達(dá)性，在多障礙、低速網(wǎng)絡(luò)環(huán)境下具有較高的應(yīng)用價值。

關(guān)鍵詞：RSSI；虛擬網(wǎng)絡(luò)；數(shù)據(jù)可達(dá)性；低速組網(wǎng)算法

DOIDOI：10.11907/rjdk.171172

中圖分類號：TP312

文獻(xiàn)標(biāo)識碼：A 文章編號文章編號：1672-7800（2017）008-0046-04

0 引言

無線傳感器網(wǎng)絡(luò)（Wireless Sensor Network，WSN）是由大量集成有信息采集、數(shù)據(jù)處理和無線通信功能的節(jié)點通過無線通信方式組成的無線自組網(wǎng)多跳網(wǎng)絡(luò)[1]。無線抄表技術(shù)是無線傳感器網(wǎng)絡(luò)發(fā)展的產(chǎn)物，它取代了傳統(tǒng)的人工抄表方式，是無線傳感網(wǎng)的一個重要應(yīng)用。重慶理工大學(xué)設(shè)計的基于GPRS的無線抄表系統(tǒng)[2]，基本可以實現(xiàn)無線抄表要求，但成本較高，不適合大面積使用；山東農(nóng)業(yè)大學(xué)利用ZigBee設(shè)計的無線抄表系統(tǒng)[3]，雖然可以實現(xiàn)自組網(wǎng)，但信號穿透性不強、靈敏度低及抗干擾能力差等眾多因素，導(dǎo)致該系統(tǒng)很難應(yīng)用于實際生產(chǎn)環(huán)境；重慶大學(xué)提出的低成本和低功耗的無線抄表算法[4-5]，雖然用在建筑內(nèi)部環(huán)境，但數(shù)據(jù)可達(dá)性無法保證。

為了解決目前無線抄表技術(shù)存在的成本高、穿透性差、信號傳輸距離短以及數(shù)據(jù)可達(dá)性差等問題，本文提出一種適用于多障礙的大型建筑物室內(nèi)環(huán)境中的無線自組網(wǎng)算法——基于RSSI的多障礙低速組網(wǎng)算法，主要采用降低信號的傳輸速度提高信號的衍射能力，以此提高信號的可達(dá)性，保證數(shù)據(jù)的交付性。由于傳輸速度較低，因此采集周期較長，通過基于方向角與最短距離算法，減少路由跳數(shù)，縮短傳輸距離并減少傳輸時間。本文以信號強度作為下一跳的選擇依據(jù)，提高數(shù)據(jù)的可達(dá)性和可靠性。通過本文提出的算法，可以有效地解決多障礙、低速網(wǎng)絡(luò)環(huán)境下的數(shù)據(jù)傳輸問題，同時還可以避免路由空洞問題。

1 相關(guān)工作

1.1 基于邏輯拓?fù)浣Y(jié)構(gòu)的路由協(xié)議AODV

AODV協(xié)議[6]是逐跳地按需距離向量路由協(xié)議。AODV協(xié)議建立路由時，源節(jié)點廣播發(fā)送路由請求RREQ數(shù)據(jù)包，每個接收到RREQ的中間節(jié)點記錄到源節(jié)點的逆向路徑，然后重新廣播RREQ數(shù)據(jù)包。當(dāng)RREQ數(shù)據(jù)包到達(dá)目的節(jié)點時，利用數(shù)據(jù)包中的逆向路徑發(fā)送RREP。收到RREP數(shù)據(jù)包的中間節(jié)點，記錄到目的節(jié)點的路徑并轉(zhuǎn)發(fā)RREP數(shù)據(jù)包。節(jié)點之間需要通過廣播hello消息來維護(hù)本地鄰居表以及一跳范圍內(nèi)的鏈路。AODV協(xié)議由于節(jié)點間需要定期廣播hello數(shù)據(jù)包以及進(jìn)行路由發(fā)現(xiàn)和泛洪，當(dāng)網(wǎng)絡(luò)規(guī)模較大時，路由發(fā)現(xiàn)和泛洪將占用大量的網(wǎng)絡(luò)帶寬，嚴(yán)重時將導(dǎo)致廣播風(fēng)暴，嚴(yán)重影響傳輸效率和可靠性。在多障礙、低速網(wǎng)絡(luò)環(huán)境中，數(shù)據(jù)的可達(dá)性更無法保證。

1.2 基于地理位置的路由協(xié)議GPSR

GPSR（Greedy Perimeter Stateless Routing）算法是哈佛大學(xué)的Brad Karp和H·T·Kung[7]于2000年提出的適用于無線數(shù)據(jù)包網(wǎng)絡(luò)的基于地理位置的路由算法。節(jié)點通過GPS等定位技術(shù)獲取本機節(jié)點的位置信息，并定期與鄰居節(jié)點之間相互發(fā)送信標(biāo)消息獲取鄰居節(jié)點的位置。通過貪婪轉(zhuǎn)發(fā)算法，選擇鄰居節(jié)點中距離目的節(jié)點最近的節(jié)點作為下一跳的轉(zhuǎn)發(fā)節(jié)點。當(dāng)出現(xiàn)空洞時，GPSR算法由貪婪轉(zhuǎn)發(fā)模式進(jìn)入到周邊轉(zhuǎn)發(fā)模式。此種算法的主要缺陷在于僅僅通過位置進(jìn)行路由選擇，將會使得某些節(jié)點被頻繁選中，導(dǎo)致節(jié)點易失效。并且，周邊轉(zhuǎn)發(fā)需要消耗大量網(wǎng)絡(luò)帶寬進(jìn)行反復(fù)修正。在大型建筑物內(nèi)部環(huán)境中，由于GPS定位受到障礙物的干擾，位置定位將會不準(zhǔn)確，且建筑物內(nèi)部環(huán)境復(fù)雜，信號的傳輸易受到障礙物的干擾，導(dǎo)致信標(biāo)信號交換不成功，周期性地與鄰居節(jié)點交換信標(biāo)信息也會占用大量的網(wǎng)絡(luò)帶寬，導(dǎo)致不必要的通信開銷。這種算法不適合用在障礙物較多的大型建筑物內(nèi)部環(huán)境中。

為了解決上述問題，使得組網(wǎng)算法能夠適應(yīng)多障礙、低速網(wǎng)絡(luò)環(huán)境，本文算法借鑒基于地理位置的路由算法，應(yīng)用于樓宇供暖數(shù)據(jù)采集等無線抄表系統(tǒng)，為保證數(shù)據(jù)的可達(dá)性，提供一種高效的數(shù)據(jù)傳輸方法。

（1）信號可達(dá)性。為提高信號可達(dá)性，增強信號的衍射和穿透能力，本文采用較低的傳輸速度，節(jié)點間的傳輸速度低于9 600bps，同時，采用節(jié)點間的信號強度RSSI作為下一跳選擇的主要依據(jù)，結(jié)合實際環(huán)境中信號的傳輸距離與最優(yōu)半徑通信，選擇一個最優(yōu)鏈路狀況的節(jié)點作為下一跳路由節(jié)點，以此提高信號可達(dá)性。

（2）算法擴展性和魯棒性。相鄰節(jié)點之間，通過交換hello數(shù)據(jù)包，確定節(jié)點間的連通關(guān)系，并將所有節(jié)點的連通情況上傳至匯集節(jié)點，根據(jù)節(jié)點間的信號強度及連通情況，構(gòu)建相應(yīng)的虛擬網(wǎng)絡(luò)，一旦節(jié)點加入或退出，匯集節(jié)點可以重新構(gòu)建虛擬網(wǎng)絡(luò)，因此可以提高該路由算法的可擴展性和魯棒性。

（3）采集周期。由于采用較低的傳輸速度，雖然盡可能地保證信號的可達(dá)性，但低傳輸速度導(dǎo)致采集周期大大加長，本文采用漸進(jìn)式路由探測方式，利用節(jié)點之間的位置進(jìn)行方向確認(rèn)，使得每一跳路由的選擇都接近于匯集節(jié)點與目的節(jié)點的連線[8]，減少信號的傳輸次數(shù)和傳輸距離。同時，將虛擬網(wǎng)絡(luò)劃分成不同的簇，簇內(nèi)節(jié)點通過交換信號強度以及距離匯聚節(jié)點的距離，產(chǎn)生新的簇頭作為簇中心。由于本文不需要考慮能量問題，因此當(dāng)且僅當(dāng)簇頭節(jié)點不可達(dá)時，由匯集節(jié)點重新指派新的簇頭節(jié)點，可以減少簇內(nèi)節(jié)點的選舉和成簇帶來的帶寬消耗。數(shù)據(jù)采集也由正向采集變?yōu)槟嫦虿杉?，從最大簇頭節(jié)點開始進(jìn)行采集數(shù)據(jù)回傳，并在回傳路徑上采集的簇內(nèi)節(jié)點數(shù)據(jù)，簇內(nèi)數(shù)據(jù)經(jīng)過簇頭節(jié)點壓縮處理，減少數(shù)據(jù)通信量，提高鏈路傳輸效率。endprint

2 算法描述

2.1 信號衰減模型

無線電波在空氣中的衍射和繞透能力決定了信號的可達(dá)程度，衍射和繞射能力主要受波長的影響，波長越長，則衍射能力就越強，相應(yīng)的頻率就越低。無線電波在空氣中的傳輸速率c、頻率f和波長λ之間的關(guān)系如式（1）所示：

λ=cf（1）

同時，無線電波在空氣中的傳輸損耗可由式（2）計算得出：

Los=32.44+20lgd+20lgf（2）

式（2）中，Los為信號在空氣中傳播的損耗，單位為dB，d為實際σdB（dB）傳輸距離，f是頻率。由式（1）、（2）可得，無線電波在空氣中的傳輸損耗與頻率成正比，即信號的傳輸頻率越高，損耗越大，相應(yīng)的傳輸距離就會越短。因此，在樓宇等大型建筑物內(nèi)部的復(fù)雜環(huán)境中，由于節(jié)點部署較為分散且傳輸過程中需要穿透或繞過大量的墻壁或門窗等障礙物，通常會選用較低的頻率來提高信號的傳輸距離和信號的衍射、繞射能力。

無線電波在傳輸過程中普遍采用衰減模型——Shadowing模型[9-10]，該模型如下：

P=P0+10nlgdd0+ξ（3）

式（3）中，d0為參考距離，P0為距離d0時接收到的信號強度，其中包含了遮蔽外衰減或環(huán)境造成的損耗參考；d為實際距離；ξ為以dB為單位的遮蔽因子，其均值為0，均方差σdB（dB）為正態(tài)隨機變量；P為正在接收的信號強度；n為路徑損耗指數(shù)，依賴于環(huán)境和建筑物的類型。在實際測量過程中，節(jié)點接收到的信號強度符合以下模型，如式（4）所示：

RSSI=-（10nlgd+A）（4）

由于RSSI值受周圍環(huán)境的影響較大，具有時變特性，會偏離式（4）給出的模型，導(dǎo)致距離估算誤差較大。因此采用環(huán)境衰減因素模型[11]，如式（5）所示：

RSSI=-（10nlgd+A）-EAF（5）

式（5）中，EAF（dBm）為環(huán)境影響因素，取決于室內(nèi)環(huán)境，由實測值RSSI和理想RSSI值計算而來。RSSI為接收到的信號強度，d為實際的傳輸距離，A為距發(fā)射節(jié)點1m處的信號強度；n為信號傳輸常數(shù)，與周圍環(huán)境相關(guān)。n和A在不同環(huán)境下的取值在文獻(xiàn)[10]中給出了如表1所示的數(shù)據(jù)。

EQi=Weightvw（i）+Weightr（i）（9）

式（9）中，EQi表示第i個候選節(jié)點Ki到源節(jié)點的鏈路評估質(zhì)量，Weightvw（i）表示候選節(jié)點Ki在虛擬網(wǎng)絡(luò)中LQ的權(quán)值，Weightr（i）表示候選節(jié)點Ki在實際傳輸環(huán)境中的權(quán)值，Weightvw（i）、Weightr（i）表示如式（10）、（11）所示：

Weightvw（i）=LQi*lg（Δ）lgd（S，D） LQi>LQThreshold（10）

其中，

Δ=d（S，Ki）*cosSKi，SDWeightr（i）=LQi*lgDi∑ni=0Di LQi>LQThreshold（11）

式（10）中，LQi為第i個候選節(jié)點Ki的鏈路質(zhì)量，d（S，Ki）為發(fā)送節(jié)點S與第i個候選節(jié)點在虛擬網(wǎng)絡(luò)中的曼哈頓距離，cosSKi，SD為發(fā)送節(jié)點、候選節(jié)點和目的節(jié)點之間的夾角余弦，LQThreshold表示鏈路質(zhì)量閾值，通常由實際環(huán)境決定。通過計算出候選節(jié)點在虛擬網(wǎng)絡(luò)中的權(quán)值Weightvw（i），可以得到在虛擬網(wǎng)絡(luò)中的最優(yōu)下一跳節(jié)點。式（11）中，Di表示節(jié)點在實際環(huán)境的通信距離，根據(jù)文獻(xiàn)[10]中提供的測量結(jié)果以及現(xiàn)場實際環(huán)境中的測量結(jié)果，假定接收信號強度Rssireceive在-55 dB范圍內(nèi)表示最優(yōu)，-55dB～-65 dB范圍內(nèi)表示次優(yōu)，超過-70 dB的權(quán)值表示信號差，不作為下一跳候選節(jié)點，因此由式（5）可以計算出Di。

由式（9）～（11）可以計算出第i個候選節(jié)點的鏈路評估質(zhì)量EQi，構(gòu)成EQ集合，并選擇最大值Max{EQ1，EQ2，...，EQi，..EQn} ，n表示候選節(jié)點個數(shù)。由此可以挑選出最優(yōu)下一跳節(jié)點，既滿足跳數(shù)較少又滿足信號可達(dá)，在充分保證可達(dá)性的前提下縮短時間。

3 算法實現(xiàn)

本算法實現(xiàn)過程主要包含3部分：構(gòu)建虛擬網(wǎng)絡(luò)并分簇、選擇最優(yōu)下一跳、數(shù)據(jù)采集。

3.1 虛擬網(wǎng)絡(luò)構(gòu)建及分簇

虛擬網(wǎng)絡(luò)是由節(jié)點相互交換信標(biāo)信息，確認(rèn)節(jié)點間的相互關(guān)系，并通過轉(zhuǎn)發(fā)將消息上傳至匯集節(jié)點，由匯集節(jié)點根據(jù)基于三角形的位置估算法TBLA[12-13]確定節(jié)點位置后生成的網(wǎng)絡(luò)拓?fù)洹?/p>

虛擬網(wǎng)絡(luò)構(gòu)建步驟如下：①固定匯集節(jié)點位置和1個與匯集節(jié)點相通的鄰居節(jié)點，并測量兩節(jié)點的距離，將這兩個節(jié)點作為定位錨節(jié)點；②節(jié)點上電后開始發(fā)送hello數(shù)據(jù)包，附近可達(dá)節(jié)點收到hello數(shù)據(jù)包后，返回接收到的RSSI值，為了盡可能多地連通鄰居節(jié)點，每個節(jié)點發(fā)送3次hello數(shù)據(jù)包；

③匯集節(jié)點發(fā)出回收命令，與匯集節(jié)點連通的鄰居節(jié)點廣播自己的地址，其它節(jié)點收到該節(jié)點的廣播數(shù)據(jù)包，將本機節(jié)點與鄰居節(jié)點的連通情況上傳給匯集節(jié)點；④匯集節(jié)點將本機節(jié)點與預(yù)設(shè)的鄰居節(jié)點作為錨節(jié)點，從所有節(jié)點中挑選與錨節(jié)點相連通的節(jié)點，并按照三角形定位算法進(jìn)行定位，將已經(jīng)定位的節(jié)點設(shè)置為新的錨節(jié)點。如果某個節(jié)點的連通節(jié)點中，有大于2個錨節(jié)點，則任意挑選兩個錨節(jié)點進(jìn)行定位。最終將所有節(jié)點與錨節(jié)點的距離轉(zhuǎn)換成距匯集節(jié)點的距離，構(gòu)建虛擬網(wǎng)絡(luò)；⑤虛擬網(wǎng)絡(luò)構(gòu)建完成后，按照節(jié)點間的連通關(guān)系，根據(jù)節(jié)點間兩兩可達(dá)關(guān)系劃分成多個簇，如果某節(jié)點只與一個節(jié)點相連，則將該節(jié)點劃分到該簇。

圖1顯示了節(jié)點在實際環(huán)境中的安裝位置，每個網(wǎng)格代表一間房間，匯集節(jié)點位置固定，R為節(jié)點的最大通信半徑，由匯集節(jié)點和錨節(jié)點對其它節(jié)點進(jìn)行定位。如圖2所示，節(jié)點1經(jīng)過定位，由（1，3）位置變?yōu)椋?，2），節(jié)點0由（1，1）變?yōu)椋?，1），說明通過匯集節(jié)點與錨節(jié)點0定位時，節(jié)點1與匯集節(jié)點間的RSSI比節(jié)點1與錨點0的RSSI要強，因此，節(jié)點1更靠近匯集節(jié)點。同時，將已經(jīng)定位的節(jié)點1設(shè)置為新的錨節(jié)點。endprint

3.2 選擇最優(yōu)下一跳

最優(yōu)下一跳的選擇主要依據(jù)鏈路評估質(zhì)量EQ進(jìn)行選擇，如圖3所示。

圖3中，S表示源節(jié)點，D表示目的節(jié)點，K1和K2表示在候選區(qū)間內(nèi)的下一跳候選節(jié)點，候選區(qū)域一般選擇源節(jié)點與目的節(jié)點方向上90°范圍，具體算法如下：

1：if 目的節(jié)點是源節(jié)點的鄰可達(dá)鄰居節(jié)點 then

2： do 直接發(fā)送轉(zhuǎn)發(fā)包

3：else 根據(jù)源節(jié)點與目的節(jié)點的方向，選擇前進(jìn)方向90°范圍作為候選節(jié)點，并向候選區(qū)域內(nèi)的節(jié)點，發(fā)送鏈路探測幀，并開啟定時器等待數(shù)據(jù)回收

4：end if

5： if 定時器時間到 then

6： do 處理鏈路探測回復(fù)幀

7： if 回復(fù)節(jié)點數(shù)量Count > 0 then

8： do 計算鏈路評估質(zhì)量EQ，并選擇最優(yōu)下一跳，向下一跳節(jié)點發(fā)送鏈路驅(qū)動數(shù)據(jù)幀。

9： else 對探測幀進(jìn)行重傳，重新啟動定時器

10： end if

11：else 接收來自節(jié)點的鏈路探測回復(fù)幀

12：end if

通過上述算法，可以在候選區(qū)域內(nèi)挑選出一個最優(yōu)候選節(jié)點作為下一跳節(jié)點，并按照鏈路驅(qū)動數(shù)據(jù)幀中的指示進(jìn)行下一步探測轉(zhuǎn)發(fā)過程，鏈路探測幀中包含該節(jié)點下一跳所需探測的節(jié)點列表。

3.3 數(shù)據(jù)采集

為加快數(shù)據(jù)采集速度，減少采集周期，本文采用分簇的方式，由簇頭節(jié)點定期采集簇內(nèi)節(jié)點保存的數(shù)據(jù)。按照數(shù)據(jù)逆向采集方式，從距離匯集節(jié)點最遠(yuǎn)的簇開始進(jìn)行數(shù)據(jù)采集，同時在數(shù)據(jù)回傳過程中，采集回傳路徑上簇內(nèi)節(jié)點的數(shù)據(jù)。由于一次傳輸?shù)淖止?jié)數(shù)有限，可通過差值法對數(shù)據(jù)進(jìn)行簡單壓縮，減少字節(jié)傳輸量。

4 結(jié)語

本文提出一種面向位置信息的路由算法，該算法主要適用于大型建筑內(nèi)部的無線網(wǎng)絡(luò)互聯(lián)，選用較低頻率提高信號的繞射能力并加長傳輸距離，以此提高信號的可達(dá)性，保證數(shù)據(jù)的交付。該算法具有良好的穩(wěn)定性和可擴展性，適合在無線抄表、樓宇供暖等節(jié)點易失效、信息采集不全的工程中使用，因此該算法在多障礙、低速無線自組網(wǎng)中具有很高的應(yīng)用價值。

參考文獻(xiàn)：

[1] CADGER F，CURRAN K，SANTOS J，et al.A survey of geographical routing in wireless Ad-hoc networks[J].IEEE Communications Surveys & Tutorials，2013，15（2）：621-653.

[2] YIN XIUYAN，HOU ENZU，ZOU WENQI.The application of GPRS based communication technology in remote meter reading[Z].Relay，2006.

[3] YAN YINFA，GONG MAOFA，TANG YUANXIN.The design of zigbee based wireless network meter reading system[J].Electrical Measurement &Instrumentation，2006，43（6）：1-5.

[4] YANG F，QIU K，NIU T，et al.A low-cost and low-power wireless automatic meter reading node network routing algorithm[C].IEEE International Conference on Software Engineering and Service Science，2014：1072-1075.

[5] WANG G，QIU K，NIU T，et al.The design and implementation of an ad hoc-based wireless meter reading system[C].IEEE International Conference on Software Engineering and Service Science，2013：565-569.

[6] PERKINS B C，ROYER E.Ad hoc on demand distance vector （AODV） routing[C].Proceedings of IEEE Workshop on Mobile Computing Systems and Applications，New，2010.

[7] KARP B.Greedy perimeter stateless routing for wireless networks[Z].2010.

[8] BANERJEE I，ROY I，CHOUDHURY A R，et al.Shortest path based geographical routing algorithm in wireless sensor network[C].International Conference on Communications，Devices and Intelligent Systems，2012：262-265.

[9] AWAD A，F(xiàn)RUNZKE T，DRESSLER F.Adaptive distance estimation and localization in WSN using RSSI measures[C].Euromicro Conference on Digital System Design Architectures，Methods and Tools，2007：471-478.

[10] ZHU MING-HUI，ZHANG HUI-QING.Research on model of indoor distance measurement based on RSSI[J].Transducer and Micorsystem Technologies，2010，29（8）：19-22.

[11] 朱明輝，張會清.基于RSSI的室內(nèi)測距模型的研究[J].傳感器與微系統(tǒng)，2010，29（8）：19-22.

[12] 石為人，熊志廣，許磊.一種用于室內(nèi)人員定位的RSSI定位算法[J].計算機工程與應(yīng)用，2010，46（17）：232-235.

[13] 萬國峰，鐘俊.基于三角形理論的無線傳感器網(wǎng)絡(luò)定位算法[J].計算機應(yīng)用研究，2013，30（1）：249-251.endprint