基于位置信息的WSN數據匯聚路由算法

魏振春， 劉國棟， 衛 星， 馬學森

（合肥工業大學 計算機與信息學院，安徽 合肥 230009）

0 引 言

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

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

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

圖1 系統邏輯結構

1 BECMS網絡拓撲模型

無線數據傳輸網絡是BECMS終端節點與管理中心數據傳輸的橋梁，其傳輸性能的高低直接決定著系統的整體功能。文獻［5］對比分析了藍牙、UWB、RFID、Zigbee等 WSN無線通信技術各自應用場合，綜合考慮功耗、成本、復雜度、數據傳輸安全性等因素后，Zigbee技術成為BECMS中無線通信技術的首選。

本文設計提出的無線數據傳輸網絡中存在FFD（Full Function Device，簡稱FFD）、RFD（Reduced Function Device，簡稱RFD）2種類型的傳感器設備，這2種類型的設備各自擔任不同角色，圖1中標識為0、1的節點采用FFD設備，標識為2的節點采用RFD設備。仿真實驗中將通過仿真IEEE 802.15.4［9］MAC層協議實現對不同類型設備的支持。

BECMS中無線數據傳輸網絡的設計實現：

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

圖2 簇節點分布原理圖

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

（3）整個網絡只有1個協調器節點，網絡初始化階段協調器節點發起組建高層網絡命令，路由節點申請加入存在網絡，協調器節點對申請加入網絡的路由節點進行審核，允許審核通過的節點加入網絡。該階段結束后，路由節點和協調器節點形成該子系統高層網絡。

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

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

BECMS中設計提出的無線數據傳輸網絡形成邏輯上相互獨立的2層網絡結構模型，協調器和路由節點構成該網絡的高層骨干網絡，分布于各房間的終端節點之間不相互通信，這些終端節點僅與簇頭節點之間通信，形成該2層網絡結構模型低層網絡。

2 路由算法

本文將結合現有協議特點設計適合該模型的基于位置信息的路由算法，LBRA路由算法的前提假設為：

（1）網絡中傳感器節點幾乎不具有移動性，具有固定位置，根據節點所處房間位置，節點坐標可標示為［x，y，z］，其中｛x，y，z∈［0，Ni］，i＝1，2，3｝，設Sink節點的位置為［0，0，0］。

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

（3）終端節點啟動后進行信道掃描，申請加入已存在網絡，加入網絡的終端節點可自由運行于工作模式和休眠模式。

2.1 網絡初始化階段

2.1.1 高層網絡初始化

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

2.1.2 組建底層網絡

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

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

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

考慮到網絡規模、通信速率、時延及可靠性等因素，簇成員節點與簇頭之間的通信，采用CSMA－CA［9］通信方式，通過該通信方式來減少包沖突，提高網絡運行可靠性。

2.2 路由策略

2.2.1 數據路由選擇算法

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

節點Ssource的鄰居關系如圖3所示。

圖3 節點Ssource鄰居關系

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

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

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

2.2.2 容錯算法

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

3 實驗仿真分析

為驗證設計的有效性，在仿真軟件NS2下對協議傳輸可靠性、傳輸時延等進行仿真分析，根據BECMS中網絡拓撲結構，協調器、路由節點坐標Y值相同，可在平面區域對該網絡拓撲結構進行仿真，在100m×100m的二維平面仿真區域中，協調器節點坐標為（0，0），路由節點按坐標［X，Z］分布，網絡業務數據流設置為CBR（Constants Bit Rate）類型，模擬節點以一定周期向Sink節點發送數據，數據流開始時間為9s并持續到仿真結束，仿真時間t＝100s。

仿真過程中，網絡端到端時延定義為源節點發送分組時間到目的節點接收到該分組的時間差。為驗證算法性能表現，在同一拓撲結構下運行 LBRA、LBF（Location Based Flood，簡 稱LBF）2種協議時，同一數據流各數據包端到端時延如圖4所示，由圖4可以看出，LBRA在時延上明顯優于LBF路由協議，實時性更好。仿真過程中數據流、控制信息數據包時延抖動信息如圖5所示，圖5可以證明，采用本文設計的路由算法網絡數據包傳輸時延抖動較小，網絡運行穩定性也比較高。

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

圖4 時延分析圖

圖5 時延抖動對比

圖6 目的節點負載流量對比

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

4 結束語

本文基于建筑環境下網絡節點位置固定、拓撲可控等特性，以高可靠性、低通信時延為設計目標，提出運行于該環境的WSN 2級網絡模型，并結合已有協議特點設計適合該網絡模型的LBRA路由算法，通過仿真運行LBRA路由算法進行驗證，結果表明設計提出的WSN 2級網絡實現了網絡組建和數據通信的功能，并且可以很好地支持多跳網絡，在實時性、可靠性等方面的性能完全滿足系統的設計要求。

［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］ 張少軍.無線傳感器網絡技術及應用［M］.北京：中國電力出版社，2010：49－65.

［6］ 崔 莉，鞠海玲，苗 勇，等.無線傳感器網絡研究進展［J］.計算機研究與發展，2005，42（1）：163－174.

［7］ 王文光，劉士興，謝武軍.無線傳感器網絡概述［J］.合肥工業大學學報：自然科學版，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.