無線傳感網絡路由和定位技術研究

摘 要

無線傳感網絡在國民經濟和日常生活中得到深入廣泛的應用，承擔著數據采 集、狀態測量、設備定位等眾多功能。無線傳感網絡由大量節點通過無線自組織 方式連接而成，各個節點獨立釆集數據，按照設定的路由協議傳輸數據到中央服 務器。針對無線傳感網絡在不同領域的應用特點，發展出多種路由協議。這些路 由協議在節點能耗、數據延遲、擁塞控制等方面性能各有側重?；诘乩砦恢玫?路由協議是其中比較重要的一種，其在路由決策時主要利用節點的地理位置信息, 因而能有效控制節點能耗和快速應對網絡拓撲變化?；诘乩砦恢玫穆酚蓞f議的 基礎是節點位置信息，而基于無線信號指紋的定位算法具有成本低，定位精度高 的特點，適用于無線傳感網絡中的節點定位。本文針對無線傳感網絡中擁塞控制、 網絡能效、節點定位三個方面開展研究，并提出了相應的解決方案。本文的主要 工作內容如下：

無線傳感網絡中監控區域的異常事件產生的突發數據流會引發網絡擁塞，導 致數據包延遲增加、節點能耗增加，嚴重影響網絡的服務質量。針對能量受限傳 感網絡的擁塞問題，提出了一種基于引力競爭的擁塞控制路由算法。根據鄰居節 點間的距離位置關系和節點緩存狀態定義傳輸引力與能量引力。傳輸引力從數據 包到達率、緩存隊列長度及數據包處理能力三方面描述節點的擁塞狀態。能量引 力采用物理距離估算節點剩余能量，并考慮下游節點的能量分布。根據物理學中 功的原理，引入引力競爭強度表示位移，節點引力和引力競爭強度相乘為功，選 擇功最大的節點為下一跳節點。針對具備能量補充功能的無線傳感網絡的擁塞問 題，提岀了一種基于虛擬力的流量感知路由算法。算法依據源節點、鄰居節點以 及目的節點之間的距離關系定義虛擬內力，以構建數據包的最長單跳距離。定義 虛擬外力以感知前向區域數據流量，沿著空閑或低負載節點構建路由。虛擬外力 和虛擬內力融合成虛擬合力，從而驅動數據包避開擁塞區域，并盡快傳輸到目的 節點。

對于能量受限的傳感器節點，提高能效能夠延長無線傳感網絡生命周期，提 升網絡可用性?；诘乩砦恢玫穆酚煽梢愿鶕濣c距離選擇最佳傳輸功耗，由此 提出一種多參數融合能效路由算法。算法定義了五個路由評估參數，包括節點剩 余能量、有效轉發率、單跳傳輸比、緩存隊列指數和能量均衡度。每個參數從不 同角度反映網絡及節點的狀態。引入可信度系數評估各個參數在路由決策中的可 信程度，參數貢獻度反映各個參數之間的重要性差異。對于網絡中的隨機干擾引 起的距離測算誤差引入模糊貢獻度表示。參數貢獻度和模糊貢獻度合并為融合貢 獻度，選擇最大融合貢獻度的節點作為下一跳節點。

地理位置路由決策需要節點位置信息，此外在物流和醫療等領域的無線傳感 網絡應用中也需要對節點進行精確定位。諸多定位算法中，免測距的指紋定位算 法對節點功能要求低、定位時間短、精度高、部署成本低，近些年獲得學術和產 業界的很大關注。指紋定位包括兩個階段，離線測量階段建立定位區域無線信號 指紋與位置坐標關系數據庫；在線査詢階段根據特定算法估計未知節點坐標。本 文提出了兩種指紋定位算法，分別針對單區域和多區域節點定位。針對單區域節 點定位，提出一種基于高斯分布的指紋定位算法。首先用利用模糊方法融合未知 節點指紋與數據庫指紋形成模糊決策矩陣。算法以錨節點數量為維度建立多維高 斯分布模型，利用馬氏距離估算未知節點偏差，選擇偏差最小的K個參考節點 利用質心法估計未知節點坐標。針對多區域復雜環境定位，依據知識決策理論， 提出一種基于模糊決策的指紋定位算法。將定位過程分為三個階段：知識積累階 段，采用模糊融合形成定位決策矩陣；知識融合階段，應用拉格朗日優化算法求 得不同區域中錨節點的隸屬度權重；知識擴展階段執行定位決策，計算參考點匹 配度，將匹配度最高的參考點坐標作為未知節點的位置估算值。

本文工作圍繞無線傳感網絡的擁塞控制、能效優化和節點定位展開，以節點 間物理距離為出發點，有針對性地提出了路由算法和指紋定位算法，并通過理論 分析和軟件仿真驗證了所提算法的有效性。

關鍵詞：無線傳感網絡地理位置路由擁塞控制能效指紋定位

目錄

摘 要 I

ABSTRACT Ill

第1章緒論 1

1.1研究背景及意義 1

1.2無線傳感網絡路由研究現狀 2

1.2.1無線傳感網絡路由特點 3

1.2.2WSN擁塞控制研究現狀 5

1.2.3WSN能效路由研究現狀 6

1.2.4WSN地理位置路由研究現狀 8

1.3無線傳感網絡節點定位研究現狀 9

1.3.1無線傳感網絡節點定位 10

1.3.2WSN指紋定位研究現狀 16

1.4本文的主要研究內容及貢獻 19

1.5本文的組織結構 20

第2章 基于地理位置的WSN擁塞控制路由 22

2.1引言 22

2.2基于引力競爭的擁塞控制路由 23

2.2.1系統模型 23

2.2.2節點的引力場描述 24

2.2.3擁塞控制路由策略 28

2.2.4仿真結果與分析 31

2.3基于虛擬力的流量感知路由 35

2.3.1系統模型 36

2.3.2虛擬力流量感知路由 36

2.3.3仿真結果與分析 40

2.4本章小結 45

第3章 基于地理位置的WSN能效路由 46

3.1引言 46

3.2系統模型 46

3.3路由評價參數 47

VI

3.3.1能量均衡度 48

3.3.2單跳傳輸比 49

3.3.3有效轉發率 50

3.3.4緩存隊列指數 51

3.3.5剩余能量因子 51

3.4基于多參數融合的能效路由算法 52

3.4.1路由決策過程 52

3.4.2路由選擇策略 53

3.5仿真結果與分析 55

3.5.1調整因子的影響 56

3.5.2算法對比分析 57

3.6 本章小結 60

第4章 基于高斯分布的單區域節點定位 62

4.1引言 62

4.2定位算法基本概念 62

4.2.1基本術語 62

4.2.2信號傳播模型 63

4.3構建指紋數據庫 64

4.3.1指紋數據預處理 64

4.3.2RSS模糊融合與分析 65

4.4多維高斯分布定位算法 67

4.4.1多維高斯分布模型 67

4.4.2理想點與參考節點的距離偏差 68

4.4.3未知節點坐標估計 69

4.5仿真結果與分析 69

4.5.1定位精度評價 69

4.5.2仿真數據性能分析 70

4.5.3真實數據集測試 73

4.6本章小結 75

第5章 基于模糊決策的多區域節點定位 76

5.1引言 76

5.2知識決策理論 76

5.3模糊決策定位算法 77

5.3.1知識積累 78

VII

XI

第1章緒論

1.1研究背景及意義

近年來，海量的智能終端已連接成一個龐大的物聯網。物聯網使用諸如智能 感知、模式識別和普適計算之類的通信感知技術以實現物理世界和網絡空間的全 面集成⑴。隨著5G的普及，各種設備通過物聯網進行連接訪問將大大增加。根 據IDC的報告，到2025年全球的物聯網設備數量將達到416億臺，產生的數據 將達到79.4ZB【2］。物聯網將成為數據驅動型經濟的基礎和支柱。

作為物聯網的底層基礎接口⑶，無線傳感網絡(Wireless Sensor Network, WSN)具有功耗低、體積小、成本低、分布式和自組織的特點〔4】。許多物聯網應 用(例如環境監控⑸、智能小區［6］、能源管理［7】、智能家居［8］等)都基于WSN構 建。在數據收集、傳輸和處理過程中，WSN使用無線傳輸并將數據以單跳或多 跳的方式發送到宿節點(sink節點)或基站【9］。但傳感器節點有其自身的能量限 制，這會影響無線傳感網絡的壽命。因此，降低傳感節點的能耗、提升數據傳輸 效率和擴展網絡生命周期是無線傳感網絡領域的重要研究內容。

無線傳感網絡路由算法的主要功能是從源節點到sink節點之間規劃一條最 優路徑，數據包沿著該路徑準確、高效、快速地到達sink節點。路由算法設計策 略和優化方法對無線傳感網絡的性能具有極其顯著的影響。根據路由算法設計中 使用的輔助信息，將WSN路由算法分為兩類：基于拓撲結構的路由算法和基于 地理位置的路由算法?；谕負浣Y構的路由算法需要每個節點維護一張路由信息 表，因此節點路由決策快，在網絡穩定時能確保數據包的服務質量穩定可靠。但 需要要定期更新路由表以適應無線傳感網絡拓撲的動態變化，從而產生更多的路 由開銷。

在基于地理位置的路由算法中，節點無需存儲全局路由信息，存儲和處理開 銷較低，易于實現，具有良好的可擴展性。此類算法在進行路由決策時主要依據 使用節點的位置信息，每個節點維護一張包含鄰居節點位置信息的信息表，并定 期更新該表?；诘乩砦恢玫穆酚伤惴梢杂行Э焖夙憫獎討B變化的網絡拓撲。 但是，僅使用地理信息進行貪婪的數據轉發會對整個網絡的能源效率產生負面影 響。因此，以便在能源效率約束下實現更好的網絡性能。

無線傳感網絡節點定位指在確定傳感器節點在某個絕對或相對坐標參照系 中的位置的過程。在基于位置服務(Location Based Services, LBS)的WSN應用 中卩°】，比如地下礦井的礦工定位⑴］、醫療護理〔⑵等，節點位置信息對其功能的

有效運行至關重要?；诘乩砦恢玫腤SN路由和數據聚合也嚴重依賴定位機制。 對于許多需要定位功能的系統或應用，衛星導航定位系統(GPS、北斗等)通常 能夠滿足要求。然而，基于衛星導航的定位方法有兩個缺點卩3〕。首先，衛星導航 定位系統的定位機制要求WSN節點與多顆導航衛星滿足視距通信，但大多數 WSN部署在對無線信號有遮擋的環境，例如，高層建筑內部、室內、水下、森 林或山區，導致無法接收到有效的衛星定位信號。其次，衛星導航定位裝置價格 昂貴，會增加WSN部署成本。因此，WSN節點定位的研究重點是節點自定位技 術卩4〕。

無線傳感網絡的節點定位算法分為兩類：基于測距的定位算法和免測距定位 算法卩4】。測距類算法使用專用部件測量距離或角度，再依據簡單的幾何關系確定 節點位置。專用測量硬件，增加了傳感網部署成本。免測距定位算法具有成本優 勢。而且隨著通信技術的急速發展，近年涌現出許多基于RSS (Received Signal Strength)指紋的定位算法研究。RSS指紋定位過程分為離線測量和在線査詢兩 個階段卩5〕。離線階段將參考節點上收到的RSS信息進行統計和處理，建立指紋 數據庫；在線階段，將未知節點的RSS信息與指紋數據進行比對，從而估算未 知節點的位置。但由于WSN部署環境存儲各種干擾，導致RSS測量誤差較大且 不穩定，影響了節點定位精度。實現干擾環境下未知節點與參考節點間的地理坐 標相似度的準確衡量，維持定位精度的穩定性需要進一步的研究與探討。

1.2無線傳感網絡路由研究現狀

無線傳感網絡由大量傳感器節點以自組織方式組網而成，用于信息收集和全 面綜合監測。每個節點都具有感知、通信和計算功能。它們通過無線信號以多跳 和自組織的方式相互通信。在目前的發展形勢下，無線傳感網絡在智慧生活卩J”］、 工農業生產卩8-21］、能源領域【22-23］、災害預防和控制【24-25］、軍事應用【26］等領域得到 了廣泛的研究和應用。特別是物聯網的不斷發展，加速了無線傳感網絡技術的發 展和部署，并逐漸促進現代生活向著數字化和智能化方向演進。

無線傳感網絡中，節點之間以無線方式通信，按照自組織方式進行數據傳輸。 無線傳感網絡路由算法的功能是將源節點的數據包逐跳傳輸到目的節點，主要包 括兩個任務：一是規劃源節點和目的節點之間的最優單跳或者多跳路徑；二是該 優化路徑上的節點依次轉發數據。由于任一節點既可以感知環境、采集數據，也 可以轉發、中繼數據。每個節點都具備恢復鏈路連接、位置定位、拓撲發現和路 由決策能力。因此，無線傳感網絡中的路由算法是分布式的、路由策略可以是單 跳路由、多跳路由和全路徑路由。

能量受限的傳感器網絡中，傳感器節點由電池提供能量，大多數節點沒有外

部能源補充，因此路由算法需要考慮能量效率。同時傳感器節點由于計算能力和 存儲容量的限制，無法承擔復雜的路由計算，也難以保存全網路由信息表。此外， 由于傳感器節點數量多且節點通信范圍有限，節點通常只保存局部拓撲信息。因 此，有線和無線網絡的常規路由算法并不適用于無線傳感網絡。無線傳感網絡路 由算法所要考慮的因素也相對較多，如能量、局部拓撲信息、可擴展性、復雜度 和路由更新策略等。

1.2.1無線傳感網絡路由特點

無線傳感網絡路由于受能量、功能和通信能力的限制，源節點和sink節點 之間通常無法直接通信。數據包從源節點，通過中間節點逐條或多跳轉發，傳送 至sink節點。因此，無線傳感網絡的路由算法具有不同于傳統網絡的顯著特點【3- 52刀，主要體現在以下五個方面：

（1） 節點性能受限

由于傳感器節點成本低、體積小，其運算處理能力、數據存儲能力和網絡連 接能力都受到限制。能量受限的傳感網絡節點，常用小型電池供電、能量無法補 充。因此其路由算法的主要目標是提升節點能效，以延長網絡生命周期。路由算 法不僅考慮單個節點的能耗，還需要考慮鄰近區域，甚至整個網絡能耗。能量管 理機制是路由算法的重要組成部分。對于具備能量補充功能的無線傳感網絡，能 效不是路由算法的主要目標，算法更注重網絡吞吐率、端到端延遲等網絡QoS性 能。

（2） 網絡信息有限

傳感器節點體積小，存儲和計算能力弱，無法存儲大量路由信息并執行復雜 的路由計算。節點只能存儲自身周圍鄰近區域的局部拓撲信息，以及少量的全局 路由信息。節點需要根據有限的局部拓撲信息找到一條到目的節點的有效傳輸路 徑，這是設計傳感網絡路由算法時要考慮的基本問題。這條路徑還需要滿足能效 以及QoS要求。

（3） 以數據為中心

無線傳感網絡通常只關注監視區域中具體的物理觀測值，而不關心獲取此觀 測信息的節點，形成以數據為中心的轉發路徑。無線傳感網絡中的源節點根據應 用層業務需求感知環境和獲取數據，將數據以逐跳方式傳輸到指定的目標節點。 此過程無需在任何兩個節點之間建立固定路徑，因此路由效率是設計路由算法要 考慮的問題之一。

（4） 網絡拓撲

由于傳感器節點損壞、電源耗盡或信號干擾等因素影響，無線傳感網絡的拓

撲結構處于動態變化之中，會隨部署時間延長產生顯著變化，且變化方式難以預 測，這要求路由算法具有一定的可擴展性，能適應網絡拓撲結構的動態變化。

(5)應用相關

無線傳感網絡的應用場景有非常顯著的差異性，路由算法的設計要針對具有 應用場景具體需求進行優化。因此很難設計一種統一的、全場景路由算法。在實 際應用中，通常根據具體應用場景的特點和需求，設計與之匹配的路由算法。

1.2.1.1,無線傳感網絡路由分類

無線傳感網絡路由算法的功能是給出一系列規則，數據包按照這些規則在網 絡中進行傳輸。典型路由算法可歸類為數據中心路由、層次路由、地理位置、機 會路由和QoS感知路由。每種路由算法簡要介紹如下：

(1)數據中心路由

在大規模無線傳感網絡中，大量的節點隨機部署。由于位于同一區域的感知 節點可能會感知到相同事件，導致這些感知節點的數據包含大量冗余信息。若直 接發往sink節點，傳輸冗余信息會耗費大量能量，能量有效利用率低。數據中心 路由算法利用屬性命名聚合數據，以消除數據冗余，因此能降低能耗［28】。典型的 數據中心路由算法主要有泛洪路由、Gossiping路由、rumo路由、定向傳播路由 和SPIN路由等。

(2)層次路由

層次路由又稱簇路由。將若干傳感節點劃分為簇，每個簇按照某個規則選擇 一個節點作為簇頭。簇頭執行數據聚合、路由決策和數據轉發等功能，而簇內的 其他節點執行環境感知和數據釆集任務。層次路由算法的優點是擴展性好，且層 次拓撲結構也能獲得較高能效〔29］。典型的層次路由算法有LEACH〔3。］和TEEN【31］ 等。

(3)地理位置路由

地理位置路由使用節點間地理位置信息進行路由決策，其基礎是計算兩個節 點之間地理距離，并估算數據傳輸的能量需求，從而實現較高的能量效率和較低 的端到端傳輸延退。節點間距離可以通過接收信號強度確定，也可以使用GPS (Global Positioning System)等定位設備進行定位。典型的地理位置路由算法有 GEAR132】、GPSRD3］和 GAF【34〕等。

(4)機會路由

傳統路由算法是選擇下一跳節點，然后向其轉發數據。新節點再選擇下一跳 直到到達sink。這些算法本質上是一種確定性方法，每次只選擇一個節點，然后 必須將數據轉發到該節點。如果數據傳輸過程中，節點死亡，會導致數據丟失。

機會路由是從其鄰居節點中選擇一組節點，然后按照某種規則從這組中選擇一個 節點嘗試發送數據，如果發送成功則繼續下一跳。如果不成功，則選擇組內的另 一個節點發送，直到數據成功傳輸或者達到最大發送次數。機會路由提高了數據 傳輸的可靠性的。典型的機會路由算法有ExOR［36］、EEOR［37］和EDOR［38］等。

(5)QoS感知路由

上述路由算法也具有一定的QoS感知能力，其路由決策目標包括能效最優， 延遲最低等，但并沒有對這些指標設定具體值。QoS感知路由對網絡QoS指標 有具體的量化值需求，比如端到端網絡延遲，數據包優先級等?；诹炕疩oS指 標去設計和優化路由〔39］,可以獲得更好的傳輸質量，滿足特點領域的路由QoS 需求。SPEED®是經典的QoS感知路由算法。也有一些QoS感知路由對QoS沒 有具體值，以最大或最小某個指標為優化目標，比如最大生存期的能量路由，最 大生存期數據匯集路由、最低轉發成本路由等。

1.2.2 WSN擁塞控制研究現狀

WSN路由算法的一個主要設計目標是最大程度節省各節點能耗、實現網絡 能量均衡，從而最大限度延長網絡生存時間。但在WSN中，當許多傳感器同時 發送數據時，很可能會造成數據包擁塞；或者當某個傳感器連續不停地發送數據 包時，也有可能發生擁塞。擁塞發生時，網絡的數據包丟失率會增加，網絡整體 傳輸效率將受到影響。無線傳感網絡中的擁塞問題與傳統網絡中的擁塞問題完全 不同。當前大多數擁塞控制算法試圖通過降低源節點發送數據的速率以緩解擁塞。 但是，這種流量控制方案總是降低吞吐量。因此，擁塞控制成為WSN路由算法 設計的一個關鍵挑戰。

(1)基于負載均衡的擁塞控制

這類算法通過監測并控制各個節點的緩存隊列以達到節點間負載均衡的目 的，從而緩解網絡擁塞狀態。文獻［41］提出了一種流量感知動態路由算法TADR, 利用勢能場概念，以節點數和節點緩沖容量建立混合虛擬勢能場，充分利用空閑 或負載不足的節點，使數據包避開擁塞，最終轉發到sink。算法提升了網絡吞吐 量，降低了路由開銷。文獻［42］提出了一種基于隊列利用率的QU-RPL算法，依 據相鄰節點的隊列利用率和到邊界路由器的跳數選擇路由，實現了負載均衡并提 高了端到端的數據包交付性能。

(2)基于預測的擁塞控制

這類算法根據節點隊列狀態和其他信息預測擁塞的產生，根據預測結果調整 路由策略。文獻［43］提出的DPCC是一種分布式預測性擁塞控制算法，利用節點 的隊列占用率和信道估計器(可預測信道質量)預測擁塞，并利用節點的逐跳反

饋信息進行擁塞控制，自適應地為數據包選擇傳輸路徑，從而緩解網絡擁塞。文 獻［44］構建一個排隊網絡模型預測節點的擁塞程度，并借助水力學中的流量原理， 提出了 一種基于擁塞控制的優化路由算法CCOR。算法根據節點位置和數據包服 務速率構造網絡排隊模型，根據鏈路流量分配每條路徑的路由選擇概率，從而降 低了丟包率。文獻［45］針對認知無線網絡中的擁塞控制，提岀了一種的主動隊列 管理算法MAQ,目標是動態變化的網絡中基于多模型預測控制策略使節點TCP 隊列保持穩定。文獻［46］考慮多個因素，例如跳數、剩余能量、緩沖區占用率和 轉發率，使用模糊邏輯確定因素權重，最后使用指數平滑法進行擁塞預測。所提 算法具有高吞吐量、低丟包率，延長了網絡壽命。文獻［47］提出了一種支持向量 機SVM和人工神經網絡ANN結合的擁塞檢測和預測算法，具有較高的準確度。 文獻［48］提出的MOPC協議預測節點擁塞程度，依據節點的擁塞預知度、剩余能 量和最小跳數確定節點的轉發滿意度，進而建立路徑滿意度模型并選擇最優路徑， 降低了擁塞發生概率。

(3)基于流量感知的擁塞控制

此類算法主動感知節點流量，針對不同的流量狀態采用不同的轉發策略，從 而提升網絡吞吐量，降低丟包率。文獻［49］針對無線傳感網中的可變流量模式， 提岀了一種混合CSMA/TDMA的擁塞控制算法iQueue-MAC。算法使用基于競 爭的CSMA機制，提供低延遲和分散傳輸。當流量增加時，iQueue-MAC更改為 無競爭TDMA機制。iQueue-MAC減輕了數據包緩沖并減少了數據包延退。文獻 ［50］根據無線傳感器網絡中的數據傳輸與水管中的水流之間的相似性，提出了一 種流量感知路由算法TER。算法根據節點物理距離和流量負載構建管道模型，強 制數據包避開擁塞區域。所提算法在全局能耗、時效性和可靠性方面具有更好的 性能。文獻［51］提出了一種主動隊列管理算法AQM,結合隨機早檢測與模糊比 例積分控制器以感知網絡流量。當擁塞發生時，算法控制目標緩沖隊列，估計和 調整每個節點的發送速率，降低了數據丟包率和端到端延遲。文獻［52］提出了一 種基于優先級的流量控制機制，將流量分為高優先級實時流量與低優先級非實時 流量，并根據優先級區分服務，保證了高優先級的延遲要求。

1.2.3 WSN能效路由研究現狀

無線傳感網絡的QoS服務質量取決數據包的傳遞效率，傳感器節點采集的 數據需要快速、可靠、安全地傳遞到目的節點(sink節點或網關)。為了解決這一 問題，許多學者研究出了多種路由算法，多數路由算法只強化了某一方面的指標， 比如追求最小能耗、最大網絡壽命或最小延遲時間，無法實現多個指標的良好的 平衡。對于在復雜、危險區域部署的無線傳感器網絡，其節點通常采用一次性電

池供電，并且難以更換。針對此類能量受限的WSN,為了延長網絡的服務時間， 需要合適的路由策略以避免個別節點由于轉發大量數據而能量耗盡。因此能效成 為無線傳感網絡路由算法中的重要考慮因素。

WSN在不同的應用領域對數據傳輸的QoS要求不同，在能效約束前提下， 針對不同的目標釆用不同的方式進行優化。文獻［53］針對節點睡眠/喚醒模式時隙 調度問題，提出了一種能效多屬性時隙調度算法MATSS,對，基于距離最短和 能效最長選擇路由，以最大限度地延長網絡壽命和最大化吞吐量比。文獻［54］以 最小的路由開銷為目標，提出了一種基于三角模糊的譜聚類路由算法TF-SCR= 算法基于節點剩余能量和接收信號強度對節點應用譜聚類分組，然后應用三角模 糊隸屬函數選擇具有最高剩余能量和信號強度的節點作為簇頭。所提算法提高 WSN的網絡壽命和可靠性。文獻［55］針對匯聚節點能量消耗過快的問題，提出了 一種基于移動節點的分布式環形路由協議，可以實現負載平衡，并在全網絡中實 現能源消耗均衡。文獻［56］提出了一種新的路由協議ECFP,利用節點與Sink節 點的最短跳數建立簇首競爭半徑，選擇剩余能量較高、鏈路質量較好的節點為簇 首，然后基于虛擬力模型進行非均勻分簇，在能耗均衡性和網絡生存時長都具有 較好的性能。文獻［57］針對WSN中對時延的要求，提出了基于多路徑代價函數 的能效地理路由算法M-EEGR,綜合考慮節點間能量的統計參數、路徑能耗、網 絡總能量和路由跳數，并通過DATF優化算法使路徑上節點個數最小化，滿足時 延需求，保證網絡QoS的同時，實現了網絡能量消耗的均衡。

路由決策過程中考慮節點的剩余能量，并嘗試使用高能量節點轉發數據以延 長網絡壽命。同時，引入距離因素可以在一定程度上避免能耗過高和較長的傳輸 路徑。文獻［58］提出了一種自適應動態多約束路由方法，基于多屬性決策方法進 行動態路由選擇，通過延長高連接節點的生命周期和優化數據傳輸提高網絡生命 周期。文獻［59］針對關鍵節點能耗過快的問題，提出了一種基于下一跳節點剩余 能量動態調整前向角度的蟻群路由算法DAFARE。算法將剩余能量和節點距離 引入蟻群算法概率轉移函數，根據前向角度范圍內節點剩余能量情況剩動態調整 前向角度大小，避免了關鍵節點過早死亡。文獻［60］設計了一種基于剩余能量和 通信代價的路由算法。該算法依據剩余能量選擇簇首，然后依據最小通信代價和 最大剩余能量選擇下一跳，實現了各節點能耗均衡。文獻［61］提出了一種基于 LEACH的能效分簇路由策略。此策略根據兩種能量級別分簇；選擇能量較低的 普通節點作為簇成員，選擇更多剩余能量的節點作為簇頭。同時，該策略以到達 sink的最小距離作為路由標準。在文獻［62］中，作者提出了基于剩余能量級別的 分簇協議CPREL,可以有效地平衡所有節點的能量消耗并延長網絡壽命。文獻 ［63］提出了基于非線性權重粒子群優化路由算法NWPSO,同時考慮能量效率和 傳輸距離，從而延長網絡生命周期。文獻［64］提出了基于改進蟻群算法的路由算 法，分析節點距離、傳輸方向和剩余能量，計算出源與目標之間的最佳路徑，從 而降低網絡能耗，延長網絡生命周期。

上述研究都是基于數據傳輸的能效優化展開，通過均衡流量負載和減少控制 消息的傳輸能間接降低WSN的能耗。文獻［65］提出了一種基于樹的隨機切換算 法RaSMaLai,將一些傳感器節點從其原始路徑隨機切換到其他負載較低的路徑， 以實現全網節點的負載均衡，進而達到延退WSN生命周期的目的。文獻［66］針 對無線傳感網絡中的鄰居發現服務，提出了一種TMLL模型，設計了 Nihao鄰 居發現協議。協議通過控制信標減少鄰居發現協議中的空閑偵聽，降低控制信標 的信道占用率，降低了節點控制消息的能量開銷。

文獻［67-69］表明實施能量平衡路由也是延長網絡壽命的有效手段。文獻［67］ 提出了一種基于博弈論的分布式路由算法。算法通過平衡區域間和區域內節點通 信負載，延長了網絡壽命。文獻［68］將監測區域建模為以sink為中心的同心區域， 并提出消除能量孔的機制。此機制平衡了環中總節點的能量損失，并延長了網絡 壽命。為了有效地減少和保持網絡能量平衡，文獻［69］針對條狀WSN提出了一 種基于精確距離的傳輸方案，旨在實現不同區域的最佳傳輸距離，從而使網絡壽 命達到最大值。

1.2.4 WSN地理位置路由研究現狀

在WSN路由算法中，地理位置路由由于其良好的可擴展性和高效率，在無 線傳感網絡路由算法中獲得廣泛關注。傳統地理位置路由算法采用貪婪策略轉發 數據卩?！?，利用本地位置信息而非全局拓撲信息建立路由，選擇最接近目的節點的 鄰居作為下一跳節點。貪婪路由策略完全依據鄰居節點和目的節點間的地理距離。

然而，在基于地理位置路由在數據傳輸中，由于節點間的無線鏈路可靠性較 差，簡單貪婪轉發導致丟包率比較高。在能量受限的WSN中，簡單貪婪轉發導 致傳感器能量無效消耗，造成節點過早死亡，形成路由空洞PH,導致網絡生存期 縮短。因此，提高能效、實現負載平衡和延長網絡壽命是無線傳感網絡地理路由 的重要考慮因素。此外，地理位置路由設計中還需要避免路由回路，防止數據包 反向傳遞，造成能量損耗和延時增加。

路由空洞是指節點收到信息后，無法再將其轉發到目的節點附近。貪婪路由 策略選擇最近的鄰居節點轉發數據，往往會導致造成路由空洞。針對路由空洞問 題，文獻［71］提出了一種REACT地理路由算法，利用sink節點的通信距離和 RSSI,通過在每一步自選下一跳，同時執行數據聚合和構建路由。所提算法實現 了有效的數據傳輸，克服了貪婪轉發的不足。文獻［72］提出了一種能量感知雙路

8

徑地理路由協議EDGR, EDGR利用節點地理位置信息、剩余能量和能耗特性自 適應地進行路由決策，并實現了節點間負載均衡，有效地解決了資源受限WSN 中的路由空洞。

能效是能量受限的WSN中的一個關鍵問題，地理位置路由同樣也需要關注 能量的有效利用。文獻［73］提出了一種節能的多播地理路由協議EMGR。EMGR 按照預先設定的能量指標選擇一組目的節點和源節點組成能量感知組播樹，以引 導組播消息傳遞，并自適應地選擇最接近能量最優中繼位置的節點作為下一跳。 提出協議在低能耗、控制開銷、計算復雜度和高數據包交付率方面實現了提升。 文獻［74］設計了基于分簇的地理路由算法GRCS,引入了分簇機制，實現了動態 優化路由，定期選出的新簇頭會選擇最近的節點用作轉發數據，從而使能源消耗 更加均衡。

在能量無限的WSN中，路由算法的目標提高數據傳輸質量，即降低丟包率 和端到端延遲，提高數據交付率等。文獻［75］提出了一種基于位置輔助的定向緩 存代理路由協議D-CALAR,其組合了位置和地理輔助多播(Geocast),提高了 數據包的傳遞率，降低了平均延遲。

地理位置路由的基礎是節點要掌握鄰居節點的位置或距離信息，路由決策首 先要確定節點間的距離關系。文獻［76］提出了一種節點坐標恢復方法，在節點部 署時將所有節點的地理坐標編碼后保存在每個節點中，每個節點根據保存的坐標 以貪婪路由方式傳輸數據，克服了貪婪路由易陷入局部最小的特點。文獻［77］針 對貪婪路由應用中的節點坐標構建問題，提出了一種貪婪距離向量路由協議 GDV和虛擬定位協議VPoD。VPoD為每個節點分配一個虛擬空間位置，GDV根 據節點間的虛擬歐式距離選擇路由，所提算法對動態網絡具有很好的適應性。文 獻［78］針對WSN中距離估計問題，提出了一種InPhase方案，通過IEEE 802.15.4 芯片的相位測量并結合功率譜密度，推算節點之間的距離。

1.3無線傳感網絡節點定位研究現狀

無線傳感網絡廣泛應用于各行各業，承擔著直接感知客觀世界的功能。在有 些無線傳感網絡應用中，傳感器節點位置信息對于感知數據非常重要，比如軍事 應用、山火監控、醫療護理等。節點位置信息和感知數據緊密耦合，缺少位置信 息的數據會毫無意義。比如突然事件檢測，只要知道事件的具體位置，才能根據 采集的數據做出正確的決策。山火監控中，傳感器節點釆集的數據必須知道確切 的位置，才能在及時確定山火的區域和位置坐標。在基于地理位置的路由中，路 由決策的前提是節點知道鄰居節點的位置或者是與鄰居節點距離，根據這些位置 或距離信息選擇最佳路由。路由的效率和能耗取決于節點坐標和位置的精確性。

確定節點位置最簡單的方式是在部署無線傳感網絡的時候，測量節點位置。 但這種方式不適合通常無線傳感網絡的隨機部署。給節點配備衛星導航模塊，依 靠衛星導航精確定位節點坐標。但衛星導航模塊價格昂貴且能耗過高，不適用于 于微小型、廉價傳感網絡使用。而且在地下、室內等惡劣環境中，根本無法接收 衛星導航信號。因此，低成本、高精度的無線傳感網絡節點定位研究稱為無線傳 感網絡的一個研究熱點。

通常的無線傳感網絡定位算法是在定位區域部署少量位置精確、功能強大的 信標節點，信標節點的信號發射范圍覆蓋整個定位區域。未知節點測量信標節點 的信號指標，在結合其他幾何或者概率算法從而推算未知節點坐標。算法的區別 在于測量的指標和推算算法不同，導致不同的定位精度。定位算法還要考慮無線 信號傳播時的不確定性以及定位環境干擾對定位精度的影響。

1.3.1無線傳感網絡節點定位

無線傳感網絡節點定位算法通?？煞譃閮深悾夯跍y距的定位算法(Range- Based)和免測距定位算法(Range-Free)?；跍y距的算法通過測量未知節點與 信號發射節點之間的無線信號角度或傳播時間，利用幾何關系推算節點未知。測 量的信息包括接收信號強度RSS (Received Signal Strength).信號到達時間(Time of Arrival, To A)㈣、信號到達時差(Time Difference of Arrival, TDo A )網以及 信號到達角度(Angle of Arrival, AoA)団〕。這些算法通常需要部署特殊部件獲取 這些變量，并通過多次測量以提高定位精度，導致產生較高的部署成本。相比之 下，免測距定位算法只需錨節點和網絡連接的信息，因此在部署上成本更低，無 需額外的硬件支持，但定位精度有限。

指紋定位算法屬于免測距定位算法，需要在定位區域預先布設若干位置固定 的錨節點和參考節點，錨節點以額定功率持續發射無線信號，在每個參考節點位 置測量各個錨節點的信號RSS。單個參考節點位置和其測量的RSS組成位置指 紋，簡稱指紋。未知節點也測量各個錨節點的RSS,并于己有的指紋進行模式匹 配，從而確定節點位置。指紋定位算法不僅部署成本低，而且在復雜多變的傳播 環境中，如多徑和NLOS (Non-line of Sight)環境，具有更準確的定位性能，因 此近些年得到廣泛研究和應用。

1.3.1.1.基于測距的定位算法

測量定位算法的定位過程分兩個步驟：一是未知節點進行距離/角度測量， 二是將測量結果整合并計算節點位置。

(1)信號測量

測量方式對基于測距的定位算法性能有著重要影響。常用的信號測量技術包 括以下四種性 信號強度指示RSS、到達時間ToA、到達時差TDoA和到達角度 AoAo

•信號強度指示RSS

RSS表征節點接收到的信號強度的大小，單位是dB。某點的無線信號強度 與該點到信號源距離的平方成正比，這種關系構成了 RSS定位的基礎。若已知 發射節點的信號功率，接收節點通過接收信號強度估算其與發射節點間的距離。 信號強度指示的優點是不需要專用硬件，傳感器自身的無線收發設備自帶RSS 測量功能。而在實際應用中，定位環境中的物理障礙（如墻壁、人體等）會吸收 和反射無線信號，而不同的環境對無線信號的傳播有不同的影響。因此，在真實 環境中，RSS測量容易受到噪聲干擾，導致實際RSS與距離關系很少與理論一 致。

•到達時間TO A

TOA表示無線信號在兩個節點之間傳播所用的時間。測量TOA需要發射節 點和接收節點具備同步時鐘。發射節點發出的定位信號中包含了發射時間，當信 號到達接收節點時，它會記錄到達的時間，并計算出信號的傳輸時間，結合光速 估計兩個節點之間的距離。TOA測量的主要缺點包括：需要精確時鐘同步；多徑 效應導致記錄接收時間比較困難；在定位信號中加入發射時間，增加了通信開銷。

•到達時間差TDOA

TDOA指兩種速度不同的信號或者兩個發射節點發出的信號到達同一節點 的時間差值。TDOA不必測量無線信號傳播的絕對時間，因此無需節點間的時間 同步。根據無線信號到達時間與第二個信號（通常為音頻信號）之間的差異計算 兩個節點間的距離。如果采用兩種信號計算時間差，則需要為每個節點裝備音頻 接收裝置。發射節點發送無線定位信號，等待間隔，后發送聲波信號。接收節點 在收到無線定位信號時，同時開啟音頻接收裝置以檢測傳入的音頻信號?；?TDoA的定位有較高的準確度，但音頻裝置提高了成本。

•到達角度（AOA）

AOA表示接收節點收到信號的方向與某一水平線（包含發射節點的水平線） 間的夾角度數，也稱為信號方向相對于接收節點的到達角。當節點接收定位信號 時，根據不同位置的接收裝置收到信號的不同相位，計算處信號到達角度，確定 信號發射節點的位置。測量信號的不同相位，需要配備多個信號接收陣列單元。 接收陣列單元的數量、單元間距以及SNR （Signal-to-NoiseRatio）都會影響定位 性能。但WSN小巧的節點也無法設置多單元接收陣列，因此AOA技術面臨的主要挑戰是昂貴的硬件成本。

(2)節點位置計算方法

根據測量的信號角度、到達時間和信號強度，利用特定方法就能確定節點位 置坐標。最常用的方法是三角測量法、三邊測量法和概率法。計算過程中，錨節 點的坐標和間距是已知量。三角測量法使用節點方位角進行定位，而三邊測量法 使用節點間的距離定位節點。最常用的概率法是極大似然估計MLE (Maximum Likelihood Estimation)和貝葉斯推理。

• 三角測量法(triangulation)AoA測量獲得未知節點相對于錨節點的方位角a和0,如圖1-1所示。根 據公式(1-1)計算未知節點的垂距d,就可以推算岀未知節點坐標。

 

式中，Z為錨節點1和錨節點2間的距離。

 

 

 

• 三邊測量法(trilateration) 三邊測量法如圖1?2所示，未知節點根據獲取的錨節點RS，值，換算為距

離節點之間的距離凡，根據公式(1-2)確定自己的坐標。

(x-x^ +(y-y^ =Rf z = 1,2,3

•概率法

概率法使用無線信號概率模型表示系統狀態和測量數據間的關系。在極大似 然估計MLE中，系統狀態參數通過最大化測量數據似然度得到。MLE用于對沒 有先驗信息的模型參數進行估計。貝葉斯推理系統使用先驗息和測量數據進行估 計，然后應用貝葉斯定義反復迭代得到未知節點坐標。

12

 

圖1?2三邊測量法示意圖

Fig. 1-2 Illustration of trilateration

 

1.3.1.2.免測距的定位算法

相比基于測距的定位算法，免測距定位算法無需配備昂貴的測量裝置，降低 了定位成本。免測距定位算法可概括為三類，即基于錨節點近似算法、基于連接 的算法和事件驅動的算法。

(1)基于錨節點近似算法

此類算法在定位區域布設若干錨節點和參考節點，錨節點具有發射信號(無 線信號、紅外或聲音)功能。首先根據某種模式大致確定出未知節點周圍的錨節 點數量。然后再利用其他方法確定節點位置。最常用、最簡單的方法是質心法。 設網絡中布設了 〃個位置已知的錨節點，錨節點坐標為3雙)通常將錨 節點排列為規則的網狀拓撲，比如矩形網狀拓撲。未知節點根據某種模式選擇岀 周圍的若干錨節點，這些錨節點連接成一個多邊形，多邊形的質心就是未知節點 位置。為了最大限度地減少定位錯誤，該方法需要密集的錨節點網絡。為了降低 定位成本，可以使用虛擬節點代替部分錨節點，虛擬節點不發射信號，只代表該 點的坐標和信號測量值。

(2)墓于連接的算法

此類算法利用全網的連接信息做岀定位決策。其中最著名的一個算法是DV- hop。該算法以距離矢量路由為核心，每個錨節點廣播包含其位置坐標的信標消 息。信標中的跳數初值為1,每經過一個節點加1。當多個錨節點的信標在網絡 中傳輸時，傳輸路徑上的每個節點都會記錄各個錨節點的最小跳數。在各向同性 的傳感網中，信號的單跳物理距離在各方向上大致相同。未知節點根據跳數估算 到各個錨節點的距離。但在復雜網絡中，由于存在干擾等因素，導致各個方向單 跳距離差異較大，難以實現精確定位。

(3)事件驅動的算法

此類算法中，不屬于無線傳感網絡的設備提供定位信號，傳感網絡不傳輸定

位數據。傳感器節點不參與定位活動。比如燈塔算法㈤］根據節點停留在外部定位 設備生成的平行旋轉光束中的持續時間對節點進行定位。聚光燈算法基本上遵循 與燈塔方法相同的機制，區別在于，它在聚光燈設備上完成定位算法所需的資源 密集型運算，而非在傳感器節點上運行，從而降低了傳感器功耗和成本。

1.3.13.指紋定位算法

指紋定位是免測距定位算法中獲得較多關注的一種定位算法卩4】。在定位區 域布設一定數量的錨節點，錨節點位置固定，坐標已知，具有信號發射功能。傳 感器節點測量各個錨節點無線信號強度RSS。測量的RSS值和該節點的位置坐 標稱為該位置的信號指紋。指紋定位方式不依據RSS與距離公式推算節點位置， 而是融合RSS與錨節點近似算法推算傳感器節點位置。指紋定位算法需要在定 位空間建立指紋數據庫，即將空間各點的位置坐標與該位置處不同錨節點的RSS 信息建立聯系。指紋定位過程就是根據指紋數據庫的指紋和位置關系信息，將未 知節點接收到的RSS信息轉化為位置信息。將RSS轉化為目標位置的過程即為 指紋匹配及指紋定位。指紋定位也能描述為一個多重假設檢驗問題，根據預先獲 得的觀察結果（即指紋）推導出最佳假設（目標的位置）。指紋定位過程也可認 為是一個決策過程，根據己有信息（指紋數據庫）和未知節點測量的RSS,決策 目標為未知節點位置。

指紋定位算法需要兩個階段：離線測量階段和在線定位階段。圖1-3為指紋 定位的基本流程。在離線測量階段，首先在當前定位環境中布設一定數量參考節 點，并記錄所有參考點的位置坐標。通常參考節點按網格狀布設，參考節點可以 為物理節點，也可以為虛擬節點。然后在所有參考節點處按某種方式測量、收集 各個錨節點的RSS值，稱為原始觀測數據，或稱為樣本。由于定位區域不可避 免存在信號干擾，RSS的測量值存在誤差，需要采用一定的方法對樣本進行預處 理。預處理后的RSS數據和參考節點的坐標建立對應關系，形成指紋數據庫。

在線定位階段，目標節點在自己位置測量各個錨節點的RSS值，并發到后 臺定位服務。定位算法將此RSS值與指紋數據庫所有樣本按照設定的算法進行 匹配，找出一個或多個匹配度最高的參考節點。最后將這些參考點位置坐標按照 特點算法轉換為目標節點所對應的位置，即目標節點的位置估計。