WSN跟蹤中基于鏈路質量的動態簇簇內通信機制

辛 玲，陳 滌，李耀偉

(山東大學信息科學與工程學院，濟南250100)

WSN中基于動態簇的目標跟蹤機制主要包括動態簇的管理和目標的定位與預測兩部分。動態簇的管理包括初始簇的創建(競選簇頭、招募簇成員)和簇結構的調整(變換簇頭、簇成員的添加或刪除)［1－3］。目標定位算法有 TOA、TDOA、AOA、RSSI、質心算法、凸規劃、DV-Hop、MDS-MAP、APIT 等。目標預測算法有軌跡擬合、線性預測、卡爾曼濾波［4］、粒子濾波［5］等。本文主要討論WSN目標跟蹤中的動態簇管理部分。在目前有關動態成簇機制的文獻中，大部分研究者所采用的算法沒有考慮實際的鏈路質量問題，而是簡單假設當節點間的距離小于通信半徑時，數據包接收率PRR=100%，大于通信半徑時，PRR=0。這種假設在實際應用中會對算法的性能造成很大的影響，實際的無線信道的自由衰落、陰影衰落等造成通信過程中發生丟包，鏈路不可靠，解決這一問題的最簡單方法就是數據重傳，而數據重傳對能量有限的無線傳感器節點既會造成節點能量的消耗，也會帶來延時等問題，不適用對實時性要求較高的情況。圖1［6］為發射功率0dbm時連接區、過渡區的范圍和在過渡區PRR的變化情況。由圖1可知，過渡區存在非常高的不可靠鏈路。

為此本文將衡量鏈路質量的指標LQI作為選擇簇頭的影響因子之一，在簇成員與簇頭通信時采用多跳可靠通信方式代替多數文獻所采用的單跳通信方式。

圖1 短距離無線信道模型

1 動態簇跟蹤機制

1.1 初始動態簇的組建

本文中，跟蹤目標在移動過程中周期發送射頻信號，傳感器節點隨機分布在監控區域，為了節省電量，目標未出現在監測區域時，所有節點處于周期性偵聽休眠狀態，目標第一次出現在監測區域時，監測到目標的節點競選簇頭，并招募簇成員，形成初始簇。

當節點的通信半徑大于等于兩倍的目標的傳輸半徑Rt，即Rs≥2Rt時，監測到目標的所有節點之間都可以實現相互通信。本文假設Rs=2Rt。

1.1.1 競選初始簇頭:

目標進入監測區域后，監測到目標的節點競選簇頭。在選擇簇頭時把鏈路質量指示LQI(Link Quality Indication)也作為考慮的因素。Zuniga在文獻［6］中證實了無線鏈路中連接區、過渡區、非連接區的存在，并給出了這3個區域中單位時間內接收器成功收到的數據包個數占發送器已發送包個數的比例PRR(Packet Reception Rate)的變化情況。假設兩個節點的距離為 d，定義在連接區內 PRR＞90%，在過渡區內10%≤PRR≤90%，在非連接區內PRR＜10%［6］。PRR是最能明確、直觀反映鏈路質量的指標，但獲得PRR需要發送足夠大數量的探測包，會引發能量消耗、信道阻塞、延時等一系列的問題。RSSI和LQI是衡量鏈路質量的另外兩個指標，并且可以由無線射頻芯片直接獲得。LQI的取值范圍是0～255，大于RSSI的取值范圍，且精度較高。另外LQI可以直接從MAC層讀取，無需轉換。考慮到LQI可以做歸一化處理，并且文獻［7］已證明LQI均值與PRR有很好的相關性，所以本文選用LQI作為衡量鏈路質量的指標。目前，并不是所有的無線射頻芯片都能提供LQI值，Mica2之前的通信芯片只能提供RSSI值，而Chipcon公司后續產品如MicaZ，Telos等產品均既可以提供RSSI值，又可以提供LQI值［8］.在網絡初始化時，節點通常利用802.15.4協議定期發送廣播“Hello”消息，并計算其與鄰居節點之間的正向及反向幀的LQI均值評估鏈路質量。LQI均值μlqi的計算如下式:

m為測得的LQI值的數目。

LQI值的變化范圍在0～255之間，可使用下面的公式對其進行歸一化處理［9］，使LQI值變化范圍在0～1之間

其中μlqi－ij表示節點i到節點j鏈路的LQI均值。網絡中節點 i和節點 j分別計算出 μlqi－ij和 μlqi－ji。μlqi－ij≠μlqi－ji，不具有對稱性。利用下面的公式可得出監測到目標的節點i與其他節點之間的平均鏈路質量:

N為監測到目標的節點的數目。

μlqi－i越高，表明該節點與其他節點的平均鏈路質量越高，數據包接收率越高，有利于增強鏈路的穩定性，減少能量消耗和時延。

設t0時刻感應到目標的節點i(i=1，2，3…，N)當前相對剩余能量ei=Ei/Emax(0＜ei≤1)，Ei為節點當前剩余電量，Emax為節點最大電池電量，節點距目標的距離di，考慮鏈路質量的影響，我們根據下面的模型選擇簇頭:

其中Rs為傳感器節點的感知半徑。α、β、γ為權衡因子，取正數。e0為節點工作所需要的最小相對剩余能量。根據實際的需求可以通過設定α、β、γ的值改變各個影響因素的權重。由式(4)可知，剩余能量越大，距目標越近，與監測到目標的其他節點之間的平均數據包接收率越高的節點，其A1值越小。目標進入監測區域，監測到目標的節點中選Ai值最小的節點擔任簇頭。

1.1.2 招募簇成員

選舉出簇頭后，簇頭就進行簇成員的招募，競選簇頭失敗的節點成為候選簇成員。競選簇成員的節點如果相對剩余能量小于e0，則退出簇成員的競選，轉入睡眠狀態。由文獻［7］，LQI均值通常在50到110之間，在發射功率為0 dBm時，PRR為10%時，LQI均值大約為65，PRR為90%時，LQI均值大約為90。考慮簇成員 j與簇頭 i之間的鏈路 j－＞i，若 μlqi－ji＜65/255，則該鏈路位于非連接區;65/255≤μlqi－ji≤90/255，則該鏈路位于過渡區;若 μlqi－ji＞90/255，則該鏈路位于連接區。若簇成員選擇鏈路質量μlqi＞90/255的節點作為下一跳節點，則節點之間的通信為可靠通信。

首先我們先提出下面幾個概念:

(1)最優功率 能保證兩節點之間通信時的最小發射功率。

(2)可靠功率 能保證兩節點之間通信時鏈路位于連接區時的發射功率。

(3)最優可靠功率 能保證兩節點之間通信時鏈路位于連接區時的最小發射功率。

(4)單跳不可靠通信方式 兩節點之間通信方式為單跳，但通信鏈路位于無線傳輸區域的過渡區。

(5)單跳可靠通信方式 兩節點之間通信方式為單跳，但通信鏈路位于無線傳輸區域的連接區。

(6)多跳不可靠通信方式 兩節點之間通信方式為多跳，但每一跳鏈路位于無線傳輸區域的過渡區。

(7)多跳可靠通信方式 兩節點之間通信方式為多跳，但每一跳鏈路位于無線傳輸區域的連接區。

以上概念(4)～(7)中的單跳、多跳通信方式不同于目前多數文獻中的單跳、多跳通信方式。目前多數文獻中的單跳、多跳通信方式并不區分連接區、過渡區、非連接區，只要兩節點之間可以通信即可。也就是說，在這種情況下，鏈路可能位于無線傳輸區域的連接區，也可能位于過渡區或過渡區，鏈路質量不能得到保證。

在以上概念的基礎之上，針對較高鏈路質量的應用環境提出了3種對單跳、多跳通信方式的改進方案。

方案1 單跳通信方式變為多跳可靠通信方式。

如圖2所示，節點A、B之間的距離小于節點的通信半徑，采用A—＞B單跳通信的方式。在節點A、B之間的鏈路位于過渡區時，該鏈路是不可靠的。在此情況下，可以采用多跳可靠路由A—＞C—＞D—＞B。具體實現方式:選取兩節點之間鏈路位于連接區的節點作為下一跳節點，即兩節點之間的距離位于連接區范圍內。如果有多條路徑，選擇跳數最少的路徑。如果多條路徑跳數相同，則選擇每一跳距離短的路徑，以減少路徑損耗。

圖2 單跳通信方式變為多跳可靠通信方式

方案2 單跳通信方式變為單跳可靠通信方式。

如圖3所示，節點A、B之間的距離小于節點的通信半徑，采用A—＞B單跳路由的方式。在節點A、B之間的鏈路位于過渡區時，該鏈路是不可靠的。若在發射功率可調的前提下，實際的工程應用環境要求有較高的鏈路質量，可以調整節點的發射功率為最優可靠發射功率，使節點A、B之間的距離位于連接區范圍內，保證可靠通信。

單跳通信方式和單跳可靠通信方式相比，在丟包率方面，單跳可靠通信方式的丟包率要明顯低于單跳通信方式。在能量消耗方面，為實現單跳可靠通信，節點增大了發射功率，總體能量消耗肯定增大。

圖3 單跳通信方式變為單跳可靠通信方式

方案3 多跳通信方式變為多跳可靠通信方式。

如圖4所示，節點A、D之間通過多跳路由A—＞B—＞C—＞D的方式實現通信。在采用理想的通斷模型時，不能保證鏈路的可靠性。若在發射功率可調的前提下，實際的工程應用環境要求有較高的鏈路質量，可以調整每一跳鏈路(A—＞B，B—＞C，C—＞D)的節點的發射功率為最優可靠發射功率，使得每一跳鏈路位于連接區從而保證整個多跳路由的可靠通信。

圖4 多跳通信方式變為多跳可靠通信方式

多跳通信方式和多跳可靠通信方式相比，在丟包率方面，多跳可靠通信方式的丟包率要明顯低于多跳通信方式。在能量消耗方面，為實現多跳可靠通信，節點增大了發射功率，總體能量消耗肯定增大。

形成初始簇后，選用合適的通信方式。對于本文特定的跟蹤應用環境，能量有限又對實時性要求比較高，即要求較高的鏈路質量。所以本文采用方案一的改進方式。即簇成員與簇頭通信時，若簇成員與簇頭之間的鏈路位于連接區，則仍采用單跳通信方式;若簇成員與簇頭之間的鏈路位于過渡區，則采用多跳可靠通信方式，但當簇成員與簇頭之間的鏈路位于過渡區但找不到滿足連接區鏈路質量的路徑時，則仍采用單跳通信方式。

初始簇形成流程如圖5所示。

圖5 初始簇形成流程

1.2 簇成員的調整

隨著目標的移動，如果目標出了節點的監測范圍，簇成員連續3個抽樣周期沒有接收到目標信號，則向簇頭申請退出該簇。簇頭節點收到簇成員的申請后，將該節點從簇成員列表中刪除。如果有新的節點監測到目標，該節點的剩余能量大于則申請加入該簇，簇頭將該成員加入到簇成員列表中。簇成員調整流程如圖6所示。

圖6 簇成員調整流程

1.3 簇頭的調整

隨著目標的移動，目標距簇頭越來越遠，當其間的距離滿足條件dCH＞εRs(0＜ε＜1)或簇頭的剩余能量小于e0時，啟動簇頭移交機制，此時當前簇頭退化為臨時簇頭，臨時簇頭發送簇頭調整信號。簇成員在向簇頭發送目標信息的同時，與感應到目標的非簇成員節點比較Ai值重新競爭簇頭。當新的簇頭確定后，原簇頭CH發送簇結束信號，簇頭退化為普通節點。簇頭調整流程如圖7所示，整個動態簇跟蹤算法流程如圖8所示。

圖7 簇頭調整流程

圖8 動態簇跟蹤算法流程

2 目標的定位與預測

2.1 目標的定位

在某一個采樣時間t，簇頭和簇成員將接收到的RSSI值通過公式(5)得到距目標的距離d。

使用改進型無線電自由空間傳播模型［10－11］:

其中，P(d)表示節點與目標距離為d時的接收功率強度;P(d0)表示基準距離為d0時的信號強度;n表示路徑長度和路徑損耗之間的比例因子，依賴于建筑物的結構和使用的材料。節點獲得距目標的距離后，按取樣的先后將值記錄在自己的內存中，然后發送給簇頭。簇頭節點根據簇成員的位置信息和d，利用極大似然估計法對目標進行定位，得到目標在t時刻的位置。

2.2 目標的預測

目標預測就是預測目標下一時刻的位置和速度，據此進行任務和資源的重新分配。目標預測算法主要有目標軌跡擬合法、線性預測法、卡爾曼濾波、粒子濾波等。為減少迭代等復雜計算帶來的能量損耗和時間延遲，選取最小二乘法曲線估計對目標進行預測。設目標運動曲線服從下列多項式函數分布:

求得ak即可得到目標的函數分布，由此預測下一時刻的位置。

3 仿真分析及討論

3.1 目標跟蹤模型

為了評估所提出的簇內通信機制的可行性，利用Matlab對該機制進行了仿真。假設200個節點隨機分布在200 m×200 m的區域內。目標做勻速直線運動，目標初始位置為(0，0)，vx=vy=1 m/s。

圖9為t=100 s采樣時刻簇組織情況。

圖9 t=100 s時跟蹤情況

算法的參數設置如表1所示。

表1 仿真參數設置

3.2 仿真分析

3.2.1 單跳通信方式和多跳可靠通信方式的網絡平均丟包率比較分析

圖10給出了當節點總數逐漸增加時，單跳通信方式和多跳可靠通信方式的平均丟包率隨節點總數的變化情況，仿真時在不同的節點總數下各重復100次試驗，取100次實驗的平均值。由仿真結果可知，多跳可靠方式的丟包率明顯減少。因為多跳可靠通信方式不一定能找到滿足連接區鏈路質量的下一跳節點，對于這樣的節點仍采取單跳通信方式。所以多跳可靠通信方式的PRR不能達到100%。隨著節點數目的增大，能夠找到滿足連接區鏈路質量的下一跳節點的鏈路增多，所以網絡平均丟包率減少。

圖10 網絡平均丟包率仿真

3.2.2 單跳通信方式和多跳可靠通信方式的能量消耗比較分析

此處仿真的能量消耗僅限于節點發送、接收數據的能量消耗。設數據聚合比率為1。采用文獻［12－13］的能量消耗模型。在距離為d上傳輸k bit消息，其發送和接收能耗為

其中d0為閾值，文中約為87.7 m，如果距離小于閾值，采用自由空間模型，否則采用多路衰減模型，電路能耗 Eelec=50 nJ/bit，εmp=0.001 3 pJ/(bit·m－4)，εfs=10 pJ/(bit·m－2)，數據聚合能耗 EDA=5 nJ/(bit·message－1)，每次發送的數據包大小為4 000 bit。

對于節點聚合m個1 byte信息消耗的能量為

圖11 網絡能量消耗仿真

仿真時在不同的節點總數下各重復100次試驗，取100次實驗的平均值。在這里整個網絡的能量消耗是指從(0，0)運動到(200，200)，采樣周期為1 s，整個網絡通信所消耗的能量。由圖11可知，在此仿真環境下，在同一節點總數下多跳可靠通信方式比單跳通信方式更節省能量，隨著節點總數的增加，仍然有這種特點。并且，隨節點數目的增多，整個網絡的能量消耗逐漸增大。由文獻［14］，多跳路由中的每一跳間的距離越大，多跳路由相比較單跳路由而言就越節省能量。隨著目前傳感器節點的通信半徑逐漸變大，連接區范圍也相應增大，多跳可靠通信方式在能耗方面比單跳通信方式會更有優勢。

3.2.3 單跳通信方式和多跳可靠通信方式的時延比較分析

仿真時在不同的節點總數下各重復100次試驗，取100次實驗的平均值。

此處時延仿真僅考慮數據傳輸時間，未考慮二進制退避時間。監測到目標的節點只發送一個數據包，發送的數據包大小為4 000 bit。數據傳輸速率為250 kbit/s.

由圖12可知，在此仿真環境下，在同一節點總數下多跳可靠通信方式比單跳通信方式時延更小，隨著節點總數的增加，仍然有這種特點。并且，隨節點數目的增多，整個網絡的時延隨節點數目的增多而逐漸增大。單跳通信方式節點發送數據包在鏈路質量低時會數據重傳，而多跳可靠通信方式將部分單跳不可靠鏈路轉換成可靠鏈路，這部分數據不需要重傳，所以減少了時延。

圖12 網絡時延仿真

4 結束語

本文考慮了WSN跟蹤中鏈路質量對動態成簇(競選簇頭，簇內通信方式)的影響，提出了應用于跟蹤的動態簇簇內通信機制，并對性能進行了仿真分析。仿真結果表明，將鏈路質量作為競選簇頭的權衡因子，簇內通信采用多跳可靠通信方式，提高了整個網絡的鏈路質量，降低了網絡的能量消耗，減少了網絡時延。

［1］ Zhang W S，Cao G H.DCTC:Dynamic Convoy Tree-Based Collaboration for Target Tracking in Sensor Networks［J］.IEEE Transactions on Wireless Communications，2004，3(5): － .

［2］ Chen W，Hou J，Sha L.Dynamic Clustering for Acoustic Target Tracking in Wireless Sensor Networks［C］//Proceedings of the 11th IEEE International Conference on Network Protocols(ICNP’03)，Atlanta，Georgia，USA，November 4－7 2003，258－271.

［3］ 薛皓，吳銀鋒，萬江文.時間異步無線傳感器網絡的目標跟蹤動態成簇算法［J］.高技術通訊，2010，20(1):8－13.

［4］ Tian D，Georganas N D.Connectivity Maintenance and Coverage Preservation in Wireless Sensor Networks［J］.Ad Hoc Networks，2005，3(6):744－761.

［5］ Zhai Y，Yeary B.A New Centralized Sensor Fusion-Tracking Methodology Based on Particle Filtering for Power-Aware Systems［J］.IEEE Transactions on Instrumentation and Measurement，2008，57(10):2377－2387.

［6］ Zuniga M，Krishnamachari B.Analyzing the Transitional Region in Low Power Link［C］//2004 First Annual IEEE Communications Society Conference on Sensor Hoc Communications and Networks，IEEE Secon 2004，2004:517－526.

［7］ Kannan Srinivasan，Philip Levis.RSSI is Under Appreciated.Proceedings of the Third Workshop on Embedded Networked Sensors(EmNets 2006).

［8］ 朱劍，趙海，張希元.基于LQI量度的無線鏈路質量評估模型［J］.東北大學學報:自然科學版，2008，29(9):1262－1265.

［9］ 戴靠柱.WSN中基于LQI的鏈路感知地理路由.中國科技論文在線.2011，17.

［10］ Bahl P，Padmanabhan V N.RADAR:An in-Building RF-Based User Location and Tracking System［C］//Proc of Infocom’2000，Tel Aviv，Israel.2000，2:775784.

［11］丁江鵬，陳曙.一種基于跳數比的無線傳感器網絡定位算法［J］.傳感技術學報，2009，22(12):1823－1827.

［12］ Heinzelman W R，Chandrakasan A，Balakrishnan H.An Application-Specific Protocol Architecture for Wireless Microsensor Networks［J］.IEEE Transactions on Wireless Communications，2002，1(4):660670.

［13］何國圓，陳滌.基于最優簇首的高能效傳感器網絡路由協議［J］.傳感技術學報，2008，21(10):1739－1743.

［14］李小亞，黃道平，吳洪艷.無線傳感器網絡單跳與多跳路由的選擇性［J］.計算機工程，2009，35(3):1314.