傳感網絡中坐標評估機制的研究?

張 潔

（福建農業職業技術學院 福州 350007）

1 引言

傳感網絡通過網中節點的位置坐標信息可以感知到節點附近發生QoS異常事件的位置坐標。于是節點坐標評估相關技術就成為了研究的熱點。現階段，傳感網絡中關于節點位置坐標評估的常見技術有基于測距/非測距定位方案。測距［1］方案要先計算待測節點和已知節點的間距才能確定待測位置的坐標信息，而非測距方案僅僅只需知道已知節點的位置坐標信息即可通過算法評估待測節點的位置坐標。無論從分布式系統的計算復雜度、能耗、成本可控等方面，后者都不失作為定位的首選方案。

目前，關于非測距定位方案的相關算法眾多。從定位精度角度而言，研究最多的是基于距離矢量跳數加權計算算法。該算法通過增設加權系數來體現全局拓撲網絡中不同的已知節點對待測節點的間隔計算的影響力，再計算出加權平均跳距，進而獲取待測節點位置坐標信息。然而通過引入加權系數的方式提高節點位置坐標評估精度是建立在節點均衡分布于全局拓撲網絡的前提下來展開研究的。反之，當節點無規則地分布在全局拓撲網絡中，加權算法仍然通過計算已知節點加權平均跳距的方式獲取未知節點位置坐標，將與未知節點在網絡中的實際位置坐標有較大的差距。

基于此，本文提出一種旨在提高隨機［2］拓撲全局中，節點坐標計算值與實際值吻合度的評估機制。該評估機制通過對未知節點的平均跳距重新展開評估來改善待測節點位置坐標的數值精確度。

2 加權算法原理

加權算法思想是節點僅僅與鄰接節點互換各自網絡參數信息，并通過互換協議［3］使全局節點獲得距離已知節點的跳數信息。已知節點獲取全局范圍內的其他已知節點的位置信息和間隔跳數信息，算出平均跳距。待測節點與已知節點之間的間距，通過全局平均每一次跳距與兩個節點間最短路由跳數相乘來計算獲得。當待測節點搜集到三個以上已知節點的距離信息時，通過極大似然估計來獲取未知節點的位置坐標信息。加權算法思想下的算法流程如圖1所示。

圖1 加權算法流程

由圖中流程可知算法雖然通過加權方式提高了計算未知節點位置坐標的準確性，但這是建立在全網節點密度［4］分布均衡的前提下。然而在實際網絡環境中由于諸多因素導致節點在全網中的密度呈現不均。此時再將加權平均跳距視同為節點間的實際物理距離勢必導致后續定位環節出現偏差；其次，未知節點從眾多已知節點中選出距離其最近的已知節點，計算出兩節點間的平均跳距，并將該平均跳距值等同為全網中其他已知節點的平均跳距；再者，算法忽略了在節點的通信范圍內已知/鄰居節點間跳數與實際距離的客觀關系；同時，通信范圍內各類節點的規模對計算未知節點坐標位置［5］的影響程度在算法中未得到體現。上述因素累加必然導致加權算法下的節點位置坐標與實際位置坐標吻合度較低。因此，從縮小未知節點位置坐標計算值與實際值的誤差角度而言，有必要對全局節點間平均跳距重新展開評估。

3 重新評估機制

當全網中有較多節點時，網中待定位的未知節點與已知節點在跳躍過程中可能存在跳躍路徑部分重疊的情形。比如，網中距離待測節點a最近的信標節點是已知節點A，則已知節點A到已知節點B的最短跳躍路由與未知待測節點a到錨節點B的最短跳躍路由中有一部分可能是一樣的。對于這樣的情形，在計算已知節點與未知待定位節點間距的環節中要求已知節點A仍然以先前獲得的跳距作為其平均跳距。除此情形之外，所有節點的平均跳距均要求重新評估。重新評估步驟為：1）計算平均跳距。平均跳距=（已知節點A到網中其他已知節點的距離）/已知節點的最短跳躍數；2）計算算術平均值。對先前獲得的平均跳距和上述步驟獲得的平均跳距進行算數平均，并將算數平均值取代先前獲得的平均跳距；3）評估節點距離。從已知節點的位置坐標信息獲取補償數據，并結合算數平均值來評估［6］節點的距離。

算法在啟動網絡后首先通過網中節點相互轉發數據包，使全網節點獲取各自已知節點的坐標位置和跳數數據，再評估已知節點之間的平均每跳距離和實際距離。以已知節點i和已知節點j轉發的數據包為例，分別轉發數據包［IDi-Xi-Yi-HopNumberi］和［IDj-Xj-Yj-HopNum?berj］。IDi/IDj為錨節點的標志位，（Xi，Yi）/（Xj，Yj）為已知節點的位置坐標，HopNumberi/HopNumberj為跳數信息。假設SDij為兩個已知節點的實際間距，將平均跳距與兩個已知節點間的最短跳數的乘積作為評估距離PDij，求得兩個已知節點的增長指數 Zij=（PDij-SDij）/SDij。再由這對已知節點將次增長指數以廣播方式轉發給全網中其他未知節點。為了描述未知節點w對這對已知節點的偏離程度，引入誤差因數Ywij。則Ywij=PDwi+PD?wj-PDij。為使被評估的跳距更加客觀地體現出節點之間真實距離降低評估值與實際值的差距，引入加權平均法來評估跳數最短的三個錨節點的補償系數。因此在假設距離未知節點w最近的上述一對已知節點i、j的同時新增一個已知節點m。

為評估未知節點w對網中n個已知節點的偏離度［7］，引入Ywin。Ywin=PDwi+PDwn-PDin。

定義未知節點w到達已知節點i再到網中三個偏離程度最低的已知節點e、已知節點f、已知節點g的誤差因數為Ywie、Ywif、Ywig，再求得未知節點w的補償因子Bwi。

據此可得未知節點w到達已知節點j/m的補償因子Bwj/Bwm分別如下：

結合上述未知節點w距離最近已知節點i、已知節點j、已知節點m的三個補償因子［8］，對未知節點w到已知節點i、已知節點j、已知節點m的間距進行重新評估。重新評估后的距離分別為CPwi=PD?wi/（1+Bwi）；CPwj=PDwj/（1+Bwj）；CPwm=PDwm/（1+Bwm）。

4 實驗分析

4.1 實驗模型

為方便通過Matlab仿真平臺對重新評估機制的效能進行考察，實驗開始前先對仿真模型［9］和相關指標做如下設置：1）構建100m×100m的待測傳感網絡，并在全網范圍內隨機投放30個位置坐標信息明確的已知節點和70個位置坐標信息不明確的未知待測節點。2）仿真通過6次變換節點的通信半徑來考察通信范圍對算法的影響力。3）每運行一次都重新將這100個傳感節點隨機投放在所構建的網中。為了避免相同類型節點在投放過程中不夠隨機導致實驗數據不準確，故將仿真［10］模型運行400次，再對比未知待測節點經過跳距重新評估后的位置坐標與實際位置坐標的偏離度，即定位誤差。

加權算法在計算節點坐標方面的誤差較大，根本原因在于該算法默認未知節點的跳數均為一跳，就算是多跳也默認為僅一跳。再通過平均跳距和跳數的乘積來評估已知節點和待測節點的間距。顯然這嚴重降低了算法對位置坐標計算的精度，尤其是節點在全網隨機布局情形下，這樣的誤差顯得愈加明顯。而在重評機制中為了衡量定位待測節點的準確性，引入坐標誤差因子E。該因子描述的是未知待測節點經過算法計算分析后給出的評估坐標信息（Xp，Yp）與該未知待測節點在監測網絡區域范圍內的實際坐標信息（Xs，Ys）之間的差異。當監測［11］的傳感網絡范圍內有N個未知待測節點參與時，待測節點所對應的坐標誤差因子被記為

為了考察重評機制的實效性，本次實驗方案主要從以下幾個方面來實施：1）通信半徑范圍內已知節點規模占比的變化；2）已知節點占比相同的情況下，通信半徑范圍的變化；3）通信半徑范圍內全部節點規模的變化。通過實施上述三種方案來比較算法［12］優化前后在評估跳距方面的差異程度。

4.2 實驗分析

通過Matlab將100個已經/未知節點無規則地投放在如圖2所示的傳感網絡范圍內，網中節點通信半徑置為20m。其中星號表示已知節點，三角形表示未知節點。

圖2 節點隨機布局圖

圖中顯而易見，已經節點和未知節點在網絡中的密度是不均勻的，甚至出現未知節點周圍基本不存在已知節點以及已知節點周圍的未知節點稀疏現象。就是這樣的布局，使得加權算法在計算跳距［13］時出現了誤判，進而導致后續坐標計算環節進一步偏差。

如圖3所示，是加權算法為未知節點計算出來的評估值與實際值之間在距離上的偏差。從仿真圖中不難看出偏差范圍主要集中在10m～20m之間，個別節點的偏差甚至更大。造成這么大坐標偏差的主因便是上述所說的加權算法為周邊已知節點密度稀少甚至沒有已知節點參與的未知節點，計算跳距時出現了誤差，尤其多跳情形下這樣的誤差進一步加劇。而改進的算法通過補償等方式對平均跳距重新開展評估，顯著提高了實際跳距的客觀性。故在圖4所示的仿真圖中，未知節點的位置坐標評估值與實際值在距離上的差距顯著縮小。觀察該仿真圖可知，偏差范圍降至5m～10m范圍內。這與優化前坐標定位效果形成鮮明對比。

圖3 未知節點在加權算法下的評估值與實際值在距離上的差異

圖4 未知節點在重評機制下的評估值與實際值在距離上的差異

為了驗證節點通信半徑對坐標誤差的影響力，通過仿真得到如圖5所示的實現曲線圖。仿真場景中的節點通信半徑依次是20m、30m、40m、50m、60m、70m、80m。每個通信范圍均投放15個已知節點。從曲線走勢觀察到，兩種算法的坐標誤差都隨著通信半徑的擴大總體呈現降低趨勢。相對而言，重評機制的坐標誤差改善幅度比傳統的加權算法明顯的多。隨著通信半徑［14］進一步擴大，在兩種算法坐標誤差總體趨于平穩的情況下，優化的重評機制仍然略微呈現繼續降低趨勢。

圖5 兩種算法下節點通信半徑與坐標誤差關聯度

由重評機制的評估原理可知，待測區域內未知節點坐標計算的準確程度與已知節點的位置坐標息息相關。當已知節點的數量越多，位置坐標信息越明確越豐富，越有利于縮小待測節點位置坐標評估值與位置坐標實際值的誤差程度。據此原理，在待測的隨機拓撲網絡范圍內投放不同規模的已知節點：5個、10個、15個、20個、25個、30個，并將節點通信半徑范圍統一置為30M，以此考察已知節點的規模對未知節點坐標計算帶來的影響力。為了提高仿真［15］數據的客觀性，本次實驗針對不同規模的已知節點開展高達400次的仿真，運行出如圖6所示的待測節點坐標誤差曲線圖。

圖6 兩種算法下已知節點的規模對計算待測節點坐標的影響力

圖中所示的兩條坐標誤差走勢圖可知，在總節點規模不變的前提下，兩種算法表現出來的坐標誤差均和已知節點的規模呈反比關系。在該待測隨機拓撲網絡中，已知節點占比相同的情況下，采用重評機制對待測節點開展坐標計算出現的誤差有明顯的降幅。當已知節點占比超過25%以后，加權算法的坐標誤差開始趨于穩定。相比之下，此時優化的重評機制卻能夠依然呈現略微下降的態勢。

雖然拓撲網絡中投放的節點越多，越有益于對待測節點的坐標進行精準地分析和計算。但節點規模無節制的增加反而降低網絡資源使用情況。為此，在待測拓撲網絡范圍內隨機布署節點，節點通信半徑置為20m，已知節點占比5%，節點總數從100增至350。通過仿真得到如圖7所示的曲線圖。

從圖中曲線走勢看出，無論算法優化前后的坐標誤差均隨總節點數增加而總體呈現逐漸降低趨勢。當節點總規模低于250個時，兩種算法的坐標誤差下降得都較為顯著。隨著節點總數進一步增加，兩種算法的顯著趨勢開始逐漸趨緩，甚至趨于平穩。這是由于在特定區域的拓撲網絡內，節點間通信開銷隨著總節點規模過渡擴大而線性地增加，最終耗盡網絡資源導致全網阻塞。因此，改善待測節點坐標計算精度時要事先參照設定好的網絡區域大小來合理地規劃全網節點通信半徑、全網節點投放總數。否則超出了網絡承載節點的門限，定位坐標的效能性便不再持續。此外，通過該圖曲線末端的走勢仍然可見，即便在總節點過渡投放的情況下，重評機制仍自始至終表現出坐標評估誤差較低的相對優勢。

圖7 節點總規模對兩種算法坐標計算誤差的影響力

5 結語

本文通過分析加權算法運用在節點均勻投放的全局網絡中所表現出來的坐標定位誤差和算法適用的局限性，提出了一種節點隨機分布于拓撲全網且在節點通信半徑范圍內實現多跳情形下的平均跳距重新評估機制。該機制先為節點計算出平均跳距的算術平均值并將該值取代原有的跳距值，再對跳距系數進行相應補償。最后，在Matlab仿真平臺上搭建實驗模型并構建一套實驗方案來考察本文提出的評估機制與傳統的加權算法在計算節點位置坐標方面的精度對比。經過四項實驗，最終驗證了重新評估機制應用在全局感知網絡中為待測節點計算位置坐標具有更高的可靠性和準確性。重新評估機制帶來的高精度定位可為物流跟蹤、軍事偵查、智能交通、航海定位等生產實踐領域提供一定的參考意義。