基于位置信息的WSN數(shù)據(jù)匯聚路由算法

魏振春， 劉國棟， 衛(wèi) 星， 馬學(xué)森

（合肥工業(yè)大學(xué) 計算機(jī)與信息學(xué)院，安徽 合肥 230009）

0 引 言

無線傳感器網(wǎng)絡(luò)是近年來新興的一種信息獲取和處理技術(shù)，隨著低功耗芯片的出現(xiàn)以及通信技術(shù)的飛速發(fā)展，使得大規(guī)模傳感器網(wǎng)絡(luò)的實際應(yīng)用成為可能，目前研究者越來越關(guān)注于 WSN（Wireless Sensors Network，簡稱 WSN）的應(yīng)用研究，并將其研究成果廣泛應(yīng)用于環(huán)境檢測［1］、智能建筑［2］及災(zāi)難應(yīng)急［3］等領(lǐng)域。

人們在研究 WSN解決實際問題時，根據(jù)WSN應(yīng)用環(huán)境的不同設(shè)計出多種路由協(xié)議，這些路由協(xié)議在不同的應(yīng)用環(huán)境和性能指標(biāo)下各有優(yōu)勢。研究者以不同標(biāo)準(zhǔn)對這些路由協(xié)議加以分類，基于無線傳感器網(wǎng)絡(luò)中節(jié)點參與通信的方式［4－7］將路由協(xié)議分為：平面路由協(xié)議、層次路由協(xié)議。平面路由協(xié)議中網(wǎng)絡(luò)各節(jié)點地位平等、共同協(xié)作完成感知任務(wù)，但是平面路由協(xié)議的網(wǎng)絡(luò)規(guī)模受限制、可擴(kuò)展性差，常見平面路由協(xié)議有Flooding、Modified Flood、Location Based Flood［8］、SPIN 及 Directed Diffusion；相比較而言，層次路由協(xié)議適合大規(guī)模傳感器網(wǎng)絡(luò)應(yīng)用環(huán)境，可擴(kuò)展性好，對層次路由協(xié)議的研究主要集中在分簇算法、簇狀路由算法等方面，比較經(jīng)典的層次路由協(xié)議有LEACH和PEGASIS等，這些已提出的協(xié)議多數(shù)針對低功耗設(shè)計。

本文以BECMS（Building Energy Consumption Monitoring System，簡稱BECMS）為應(yīng)用背景，重點研究 WSN網(wǎng)絡(luò)結(jié)構(gòu)設(shè)計及LBRA（Location Based Routing Algorithm，簡稱LBRA）路由算法。在BECMS應(yīng)用中，根據(jù)建筑環(huán)境中網(wǎng)絡(luò)節(jié)點具有能量可持續(xù)供應(yīng)、位置固定等特性，提出WSN 2層網(wǎng)絡(luò)結(jié)構(gòu)模型如圖1所示，并設(shè)計適合該網(wǎng)絡(luò)結(jié)構(gòu)模型的基于位置信息的數(shù)據(jù)匯聚路由算法，最后通過仿真實驗驗證算法的可行性。

圖1 系統(tǒng)邏輯結(jié)構(gòu)

1 BECMS網(wǎng)絡(luò)拓?fù)淠Ｐ?/h2>

無線數(shù)據(jù)傳輸網(wǎng)絡(luò)是BECMS終端節(jié)點與管理中心數(shù)據(jù)傳輸?shù)臉蛄海鋫鬏斝阅艿母叩椭苯記Q定著系統(tǒng)的整體功能。文獻(xiàn)［5］對比分析了藍(lán)牙、UWB、RFID、Zigbee等 WSN無線通信技術(shù)各自應(yīng)用場合，綜合考慮功耗、成本、復(fù)雜度、數(shù)據(jù)傳輸安全性等因素后，Zigbee技術(shù)成為BECMS中無線通信技術(shù)的首選。

本文設(shè)計提出的無線數(shù)據(jù)傳輸網(wǎng)絡(luò)中存在FFD（Full Function Device，簡稱FFD）、RFD（Reduced Function Device，簡稱RFD）2種類型的傳感器設(shè)備，這2種類型的設(shè)備各自擔(dān)任不同角色，圖1中標(biāo)識為0、1的節(jié)點采用FFD設(shè)備，標(biāo)識為2的節(jié)點采用RFD設(shè)備。仿真實驗中將通過仿真IEEE 802.15.4［9］MAC層協(xié)議實現(xiàn)對不同類型設(shè)備的支持。

BECMS中無線數(shù)據(jù)傳輸網(wǎng)絡(luò)的設(shè)計實現(xiàn)：

（1）每個房間中設(shè)置1個終端節(jié)點，用于收集房間溫度、濕度和耗電量等傳感器節(jié)點信息，整棟建筑中的WSN終端節(jié)點基于相鄰關(guān)系按圖2所示的策略進(jìn)行分簇，采集的數(shù)據(jù)在簇頭節(jié)點融合后再傳輸給Sink節(jié)點，這些終端傳感器節(jié)點構(gòu)成該傳輸網(wǎng)絡(luò)的最底層。

圖2 簇節(jié)點分布原理圖

（2）整棟建筑中位置相鄰的每2層分成1組，每組包括若干路由節(jié)點，這些路由節(jié)點在網(wǎng)絡(luò)中擔(dān)任簇頭角色，該類節(jié)點被放置于走廊、樓梯通道中，并且采用建筑內(nèi)的市電供電。通過分簇可以把大量簇內(nèi)通信限制于簇頭一跳鄰居范圍內(nèi)，進(jìn)而減少整個網(wǎng)絡(luò)通信開銷。

（3）整個網(wǎng)絡(luò)只有1個協(xié)調(diào)器節(jié)點，網(wǎng)絡(luò)初始化階段協(xié)調(diào)器節(jié)點發(fā)起組建高層網(wǎng)絡(luò)命令，路由節(jié)點申請加入存在網(wǎng)絡(luò)，協(xié)調(diào)器節(jié)點對申請加入網(wǎng)絡(luò)的路由節(jié)點進(jìn)行審核，允許審核通過的節(jié)點加入網(wǎng)絡(luò)。該階段結(jié)束后，路由節(jié)點和協(xié)調(diào)器節(jié)點形成該子系統(tǒng)高層網(wǎng)絡(luò)。

（4）骨干網(wǎng)絡(luò)組建完成后，路由節(jié)點發(fā)起建簇命令，終端節(jié)點申請加入各簇，該階段結(jié)束后，終端節(jié)點成為與自身距離最近簇頭節(jié)點的成員節(jié)點，完成整個網(wǎng)絡(luò)的初始化。

（5）為提高網(wǎng)絡(luò)的健壯性，采用備份簇頭策略，每個簇的成員節(jié)點中有1個終端節(jié)點采用FFD設(shè)備，擔(dān)當(dāng)備份當(dāng)前簇成員信息功能。當(dāng)簇頭節(jié)點由于故障等原因失效后，該備份簇頭節(jié)點將擔(dān)當(dāng)簇頭角色，重新組建新簇。

BECMS中設(shè)計提出的無線數(shù)據(jù)傳輸網(wǎng)絡(luò)形成邏輯上相互獨(dú)立的2層網(wǎng)絡(luò)結(jié)構(gòu)模型，協(xié)調(diào)器和路由節(jié)點構(gòu)成該網(wǎng)絡(luò)的高層骨干網(wǎng)絡(luò)，分布于各房間的終端節(jié)點之間不相互通信，這些終端節(jié)點僅與簇頭節(jié)點之間通信，形成該2層網(wǎng)絡(luò)結(jié)構(gòu)模型低層網(wǎng)絡(luò)。

2 路由算法

本文將結(jié)合現(xiàn)有協(xié)議特點設(shè)計適合該模型的基于位置信息的路由算法，LBRA路由算法的前提假設(shè)為：

（1）網(wǎng)絡(luò)中傳感器節(jié)點幾乎不具有移動性，具有固定位置，根據(jù)節(jié)點所處房間位置，節(jié)點坐標(biāo)可標(biāo)示為［x，y，z］，其中｛x，y，z∈［0，Ni］，i＝1，2，3｝，設(shè)Sink節(jié)點的位置為［0，0，0］。

（2）布設(shè)于各房間的終端節(jié)點不互相通信，只與其距離最近的路由節(jié)點通信，如果路由節(jié)點不在協(xié)調(diào)器節(jié)點的通信范圍內(nèi)，則會采用多跳的路由策略，通過路由節(jié)點的中繼最終把數(shù)據(jù)傳輸給協(xié)調(diào)器節(jié)點。

（3）終端節(jié)點啟動后進(jìn)行信道掃描，申請加入已存在網(wǎng)絡(luò)，加入網(wǎng)絡(luò)的終端節(jié)點可自由運(yùn)行于工作模式和休眠模式。

2.1 網(wǎng)絡(luò)初始化階段

2.1.1 高層網(wǎng)絡(luò)初始化

Sink節(jié)點在網(wǎng)絡(luò)高層廣播Hello消息，該Hello消息包括節(jié)點自身、Sink節(jié)點位置坐標(biāo)以及到Sink節(jié)點的跳數(shù)等信息，路由節(jié)點根據(jù)收到的信息，設(shè)置其到Sink節(jié)點的跳數(shù)后再廣播該信息，并且收到Hello消息的節(jié)點發(fā)送ACK響應(yīng)幀，申請加入存在網(wǎng)絡(luò)，該階段每個節(jié)點只廣播一次Hello消息，當(dāng)收到重復(fù)的Hello消息包時，記錄路由節(jié)點鄰居信息后，進(jìn)行簡單丟棄。該階段結(jié)束后可組建成高層骨干網(wǎng)絡(luò)，并且每個節(jié)點都了解Sink節(jié)點的位置信息和自身的鄰居列表，鄰居列表項有節(jié)點ID、距Sink節(jié)點跳數(shù)及鄰居節(jié)點數(shù)。

2.1.2 組建底層網(wǎng)絡(luò)

該階段簇頭節(jié)點采用另外頻率廣播信標(biāo)幀，等待終端節(jié)點申請加入自己組建的簇。由于采用不同的信道進(jìn)行通信，故這些信號只被終端節(jié)點接收到。終端節(jié)點按信號強(qiáng)度加入與其距離最近（距離遠(yuǎn)近通過信號強(qiáng)度來進(jìn)行判斷）的簇頭節(jié)點。

簇組建完成后，簇成員節(jié)點記錄自己所屬簇頭，同時簇頭節(jié)點把簇成員信息報告給Sink節(jié)點，便于Sink節(jié)點對網(wǎng)絡(luò)進(jìn)行全局管理。該階段結(jié)束后，簇頭節(jié)點會生成簇成員列表，簇成員列表項有節(jié)點ID、序列號和剩余電量3項。

用簇頭節(jié)點位置坐標(biāo)表示該簇ID＝［x，y，z］，x＝posX－sinkX，y＝posY－sinkY，z＝posZ－sinkZ；其中Sink節(jié)點ID＝［0，0，0］。

考慮到網(wǎng)絡(luò)規(guī)模、通信速率、時延及可靠性等因素，簇成員節(jié)點與簇頭之間的通信，采用CSMA－CA［9］通信方式，通過該通信方式來減少包沖突，提高網(wǎng)絡(luò)運(yùn)行可靠性。

2.2 路由策略

2.2.1 數(shù)據(jù)路由選擇算法

BECMS應(yīng)用環(huán)境下，終端節(jié)點把數(shù)據(jù)發(fā)送給簇頭節(jié)點，經(jīng)路由節(jié)點中繼最終把數(shù)據(jù)傳輸給Sink節(jié)點，該過程形成以Ssource、Sink為端點的最佳數(shù)據(jù)匯聚路徑。假設(shè)有數(shù)據(jù)源節(jié)點SsourceID＝［X，Y1，N］，目的節(jié)點 Sink ID＝［X1，Y1，Z1］，Ssource節(jié)點從其鄰居列表中選取距Sink節(jié)點最近、跳數(shù)最少的鄰居節(jié)點作為下一跳簇頭節(jié)點，通過這種方法來減少中繼節(jié)點數(shù)，進(jìn)而減少通信延遲和能量消耗。

節(jié)點Ssource的鄰居關(guān)系如圖3所示。

圖3 節(jié)點Ssource鄰居關(guān)系

SsourceID＝［X，Y1，N］鄰居列表項見表1所列，從鄰居列表中選擇最佳下一跳簇頭節(jié)點的算法為：

表1 簇節(jié)點ID＝［X，Y1，N］鄰居列

在該實例中將會選擇［X－1，Y1，N－1］節(jié)點為下一跳節(jié)點，如果表1不存在ID＝［X－1，Y1，N－1］節(jié)點，則會執(zhí)行Select－Send（），按跳數(shù)、鄰居節(jié)點數(shù)選擇次優(yōu)下一跳節(jié)點，若存在多個節(jié)點滿足條件時，從滿足條件的節(jié)點中隨機(jī)選擇。

2.2.2 容錯算法

本文終端節(jié)點采用一種重疊分簇策略，即同一終端節(jié)點可能是多個簇頭節(jié)點的鄰居節(jié)點，該分簇策略結(jié)合備份簇頭思想是本文容錯的前提保障。在簇頭節(jié)點失效后，備份簇頭節(jié)點運(yùn)行容錯算法，向鄰居簇頭節(jié)點發(fā)送Cluster＿Create消息，備份簇頭節(jié)點收到鄰居節(jié)點ACK響應(yīng)幀后，備份簇頭節(jié)點、一跳鄰居簇頭取得時間同步后，運(yùn)行建簇算法，簇組建完成后簇頭節(jié)點將簇成員信息報告給Sink節(jié)點，便于Sink節(jié)點管理網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)。通過這種容錯策略，簇頭節(jié)點失效后仍然可以保障網(wǎng)絡(luò)的正常運(yùn)行，提高網(wǎng)絡(luò)運(yùn)行的健壯性。

3 實驗仿真分析

為驗證設(shè)計的有效性，在仿真軟件NS2下對協(xié)議傳輸可靠性、傳輸時延等進(jìn)行仿真分析，根據(jù)BECMS中網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，協(xié)調(diào)器、路由節(jié)點坐標(biāo)Y值相同，可在平面區(qū)域?qū)υ摼W(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)進(jìn)行仿真，在100m×100m的二維平面仿真區(qū)域中，協(xié)調(diào)器節(jié)點坐標(biāo)為（0，0），路由節(jié)點按坐標(biāo)［X，Z］分布，網(wǎng)絡(luò)業(yè)務(wù)數(shù)據(jù)流設(shè)置為CBR（Constants Bit Rate）類型，模擬節(jié)點以一定周期向Sink節(jié)點發(fā)送數(shù)據(jù)，數(shù)據(jù)流開始時間為9s并持續(xù)到仿真結(jié)束，仿真時間t＝100s。

仿真過程中，網(wǎng)絡(luò)端到端時延定義為源節(jié)點發(fā)送分組時間到目的節(jié)點接收到該分組的時間差。為驗證算法性能表現(xiàn)，在同一拓?fù)浣Y(jié)構(gòu)下運(yùn)行 LBRA、LBF（Location Based Flood，簡 稱LBF）2種協(xié)議時，同一數(shù)據(jù)流各數(shù)據(jù)包端到端時延如圖4所示，由圖4可以看出，LBRA在時延上明顯優(yōu)于LBF路由協(xié)議，實時性更好。仿真過程中數(shù)據(jù)流、控制信息數(shù)據(jù)包時延抖動信息如圖5所示，圖5可以證明，采用本文設(shè)計的路由算法網(wǎng)絡(luò)數(shù)據(jù)包傳輸時延抖動較小，網(wǎng)絡(luò)運(yùn)行穩(wěn)定性也比較高。

同一數(shù)據(jù)流目的節(jié)點在整個仿真過程中，不同時刻數(shù)據(jù)流量負(fù)載情況如圖6所示，由圖6可以看出，LBRA可以明顯降低網(wǎng)絡(luò)通信量，均衡網(wǎng)絡(luò)節(jié)點流量負(fù)載，節(jié)約通信開銷、提高網(wǎng)絡(luò)吞吐量。

圖4 時延分析圖

圖5 時延抖動對比

圖6 目的節(jié)點負(fù)載流量對比

通過分析多次仿真實驗結(jié)果Trace文件，對于2種協(xié)議丟包率特性，由于LBA路由算法設(shè)計特性，目的節(jié)點收到重復(fù)分組時采用簡單丟棄方法，造成一種丟包率比較高的假象。相比較而言，運(yùn)行LBRA路由算法時丟包率低于3%，這在系統(tǒng)可以接受的程度范圍內(nèi)，不影響系統(tǒng)的正常運(yùn)行，網(wǎng)絡(luò)運(yùn)行LBRA算法可靠性較高。

4 結(jié)束語

本文基于建筑環(huán)境下網(wǎng)絡(luò)節(jié)點位置固定、拓?fù)淇煽氐忍匦裕愿呖煽啃浴⒌屯ㄐ艜r延為設(shè)計目標(biāo)，提出運(yùn)行于該環(huán)境的WSN 2級網(wǎng)絡(luò)模型，并結(jié)合已有協(xié)議特點設(shè)計適合該網(wǎng)絡(luò)模型的LBRA路由算法，通過仿真運(yùn)行LBRA路由算法進(jìn)行驗證，結(jié)果表明設(shè)計提出的WSN 2級網(wǎng)絡(luò)實現(xiàn)了網(wǎng)絡(luò)組建和數(shù)據(jù)通信的功能，并且可以很好地支持多跳網(wǎng)絡(luò)，在實時性、可靠性等方面的性能完全滿足系統(tǒng)的設(shè)計要求。

［1］ Mittal R，Bhatia M P S.Wireless sensor networks for monitoring the environmental activities［C］／／Proceedings of the IEEE International Conference on Computational Intelligence and Computing Research，2010：1－5.

［2］ Pan M S，Tsai C H，Tseng Y C.Emergency guiding and mo－nitoring applications in indoor 3Denvironments by wireless sensor networks［J］.Int J of Sensor Networks，2006，1（2）：2－10.

［3］ Bames M，Leather H，Arvind D K.Emergency evaluation using wireless sensor networks［C］／／Proceedings of the 32nd IEEE Conference on Local Computer Networks （LCN）.IEEE Press，2007：851－857.

［4］ Akkaya K，Younis M.A survey on routing protocols for wireless sensor networks［J］.Ad Hoc Network Journal，2005，3（3）：325－349.

［5］ 張少軍.無線傳感器網(wǎng)絡(luò)技術(shù)及應(yīng)用［M］.北京：中國電力出版社，2010：49－65.

［6］ 崔 莉，鞠海玲，苗 勇，等.無線傳感器網(wǎng)絡(luò)研究進(jìn)展［J］.計算機(jī)研究與發(fā)展，2005，42（1）：163－174.

［7］ 王文光，劉士興，謝武軍.無線傳感器網(wǎng)絡(luò)概述［J］.合肥工業(yè)大學(xué)學(xué)報：自然科學(xué)版，2010，33（9）：1416－1419，1437.

［8］ Sabbineni H，Chakrabarty K.Location－aided flooding：an energy－efficient data dissemination protocol for wireless sensor networks［J］.IEEE Trans Comput，2005，51（1）：36－46.

［9］ Chen F，German R，Dressler F.Towards IEEE 802.15.4e：a study of performance aspects［C］／／Proceedings of the 8th IEEE Int Conf on Pervasive Computing and Communications Workshops.Mannheim：IEEE Press，2010：68－73.