辛 玲，陳 滌，李耀偉

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

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

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

圖1 短距離無線信道模型

1 動態(tài)簇跟蹤機制

1.1 初始動態(tài)簇的組建

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

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

1.1.1 競選初始簇頭:

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

m為測得的LQI值的數(shù)目。

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

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

N為監(jiān)測到目標的節(jié)點的數(shù)目。

μlqi－i越高，表明該節(jié)點與其他節(jié)點的平均鏈路質(zhì)量越高，數(shù)據(jù)包接收率越高，有利于增強鏈路的穩(wěn)定性，減少能量消耗和時延。

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

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

1.1.2 招募簇成員

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

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

(1)最優(yōu)功率 能保證兩節(jié)點之間通信時的最小發(fā)射功率。

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

(3)最優(yōu)可靠功率 能保證兩節(jié)點之間通信時鏈路位于連接區(qū)時的最小發(fā)射功率。

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

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

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

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

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

在以上概念的基礎(chǔ)之上，針對較高鏈路質(zhì)量的應(yīng)用環(huán)境提出了3種對單跳、多跳通信方式的改進方案。

方案1 單跳通信方式變?yōu)槎嗵煽客ㄐ欧绞健?/p>

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

圖2 單跳通信方式變?yōu)槎嗵煽客ㄐ欧绞?/p>

方案2 單跳通信方式變?yōu)閱翁煽客ㄐ欧绞健?/p>

如圖3所示，節(jié)點A、B之間的距離小于節(jié)點的通信半徑，采用A—＞B單跳路由的方式。在節(jié)點A、B之間的鏈路位于過渡區(qū)時，該鏈路是不可靠的。若在發(fā)射功率可調(diào)的前提下，實際的工程應(yīng)用環(huán)境要求有較高的鏈路質(zhì)量，可以調(diào)整節(jié)點的發(fā)射功率為最優(yōu)可靠發(fā)射功率，使節(jié)點A、B之間的距離位于連接區(qū)范圍內(nèi)，保證可靠通信。

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

圖3 單跳通信方式變?yōu)閱翁煽客ㄐ欧绞?/p>

方案3 多跳通信方式變?yōu)槎嗵煽客ㄐ欧绞健?/p>

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

圖4 多跳通信方式變?yōu)槎嗵煽客ㄐ欧绞?/p>

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

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

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

圖5 初始簇形成流程

1.2 簇成員的調(diào)整

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

圖6 簇成員調(diào)整流程

1.3 簇頭的調(diào)整

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

圖7 簇頭調(diào)整流程

圖8 動態(tài)簇跟蹤算法流程

2 目標的定位與預(yù)測

2.1 目標的定位

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

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

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

2.2 目標的預(yù)測

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

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

3 仿真分析及討論

3.1 目標跟蹤模型

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

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

圖9 t=100 s時跟蹤情況

算法的參數(shù)設(shè)置如表1所示。

表1 仿真參數(shù)設(shè)置

3.2 仿真分析

3.2.1 單跳通信方式和多跳可靠通信方式的網(wǎng)絡(luò)平均丟包率比較分析

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

圖10 網(wǎng)絡(luò)平均丟包率仿真

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

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

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

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

圖11 網(wǎng)絡(luò)能量消耗仿真

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

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

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

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

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

圖12 網(wǎng)絡(luò)時延仿真

4 結(jié)束語

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

［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］ 薛皓，吳銀鋒，萬江文.時間異步無線傳感器網(wǎng)絡(luò)的目標跟蹤動態(tài)成簇算法［J］.高技術(shù)通訊，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量度的無線鏈路質(zhì)量評估模型［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］丁江鵬，陳曙.一種基于跳數(shù)比的無線傳感器網(wǎng)絡(luò)定位算法［J］.傳感技術(shù)學報，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］何國圓，陳滌.基于最優(yōu)簇首的高能效傳感器網(wǎng)絡(luò)路由協(xié)議［J］.傳感技術(shù)學報，2008，21(10):1739－1743.

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