1.引言
無線傳感器網絡是近年來一個熱點研究領域，其中傳感器網絡定位技術也越來越受到人們的關注，這是因為傳感器網絡的大量應用都依賴于節點的位置信息，例如在戰場偵察、生態環境監測、地震洪水火災等現場的監控等應用中，都需要知道傳感器節點的位置信息，從而獲知信息來源的準確位置。
現有無線傳感器網絡定位系統種類繁多，實現方法各異[1][2]。具有代表性的有采用超聲波測距的TDOA(TimeDifference of Arrival)系統[3]，基于RSSI (Receive Signal Strength Indicator)的技術[4]，基于網絡連通性的質心定位算法[5]，基于多跳傳感器網絡節點間跳數的DV-Hop算法[6]等?，F有算法大多存在額外的硬件開銷，或需要較多已知位置的參考節點，而且都有較大的通信開銷，帶來了傳感器節點額外的功耗，這樣就降低了全網的生存周期。因此，需要針對無線傳感器網絡的具體場景，設計低成本，低開銷，易實現的定位算法。
2.基于路由信息的定位算法
2.1研究場景定義
無線傳感器網絡的應用場景各異，對定位的需求也各不相同。因此，在進行定位算法的設計前，必須選定應用場景進行有針對性的設計。本文選用傳感器網絡中廣泛應用的大范圍數據采集場景，例如土壤溫濕度監測、森林火險預警、智能大廈人員數據采集等，作為研究前提。
在這種場景下，數量眾多的傳感器節點分布在較大范圍的區域內，節點需要通過多跳路由將數據返回到一個或多個網關節點。所有傳感器節點不裝配GPS、超聲收發器、有向天線等額外的定位和測距設備，節點射頻模塊只具備射頻信號強度檢測能力(RSSI)，甚至RSSI能力也不具備（即只有通信功能）。為了方便下面的研究，進一步對場景作如下簡化定義：
1.傳感器節點數目表示為n,網關節點數目表示為m；
2.n個傳感器節點在區域內隨機均勻分布，自身位置為(xi,yi)均未知，其中i= 1...n；
3.m個網關節點在區域內以某種規律分布，自身位置(xi,yi)均已知，其中i= n+1...n+m；
4.傳感器節點均以一定且相同的周期采集數據，節點間相對靜止；
5.節點采用無線全向天線進行互通信，RSS測距的先驗概率分布滿足高斯分布；
2.2設計思路
而且因為數據采集任務對網絡的存活時間要求一般較高，所以降低傳感器節點的功耗，即降低傳感器節點的通信開銷就成為設計定位算法中重要的因素。而現有定位算法存在的主要問題就是通信開銷大，其中有一個重要原因是現有的研究將定位過程與網絡路由和數據采集看作獨立的過程，而事實上這兩個過程存在大量通信的重復，這樣就帶來了額外的通信開銷。本文的研究就是將路由協議與定位算法結合來減少這部分開銷，基本思路是通過在數據包上附加網絡路由信息來獲得部分節點間的連接和距離關系，然后根據這些關系來進行傳感器節點定位，該算法命名為RBSL(RoutinginformationBased Sensor Localization)。
本文選用了傳感器網絡中常用的定向擴散路由協議[7](DirectedDiffusion)作為研究的基礎。定向擴散路由協議是一種以數據為中心的路由協議，網關節點向所有傳感器節點發送對任務描述的“興趣”(Interest)，“興趣”會逐漸在全網中擴散，最終達到所有匹配“興趣”的傳感器節點，與此同時也建立起了從網關節點到傳感器節點的“梯度”，傳感器節點會沿著梯度最大的方向將數據傳回網關節點。定向擴散的原理示意圖如下圖1所示：
圖1：定向擴散路由原理示意圖
對于全網數據采集的場景，網關節點發送的“興趣”是采集所有節點數據。在建立梯度之后，每個一個傳感器節點都有一個自己對網關節點的最大“梯度”方向，即下一跳傳輸的目的節點編號(ID)。若每個傳感器節點在發送數據包末尾都附加自己的下一跳節點ID，則在每一個網關節點就都可以獲得網絡中n條鏈路的連接情況，即獲得了到一個網關節點的樹狀路由表。將m個網關節點的數據進行綜合就可以獲得更多條鏈路的連接情況。將獲得的n個傳感器節點和m個網關節點之間的連接關系表示為對稱連接矩陣L(n+m,n+m)，其中Lij= 1 表示i, j節點存在路由鏈路，反之Lij = 0表示不存在路由鏈路，其中1≤i, j≤ n+m，若1≤i≤n表示i為傳感器節點，若n
進一步的，如果傳感器節點具有RSSI，可以根據射頻信號傳輸的經驗模型估計鏈路距離dij，同樣將估計距離發往網關節點。與連接矩陣L類似可以生成對稱距離矩陣，表示為D(n+m,n+m)，其中Dij=Dji 表示i, j節點間路由鏈路的估計距離。
下一步就是根據連接矩陣L或距離矩陣D來進行節點定位。這里就需要用到MDS算法，MDS算法的全稱是多維標度分析（Multi-DimensionalScaling），是一種最早應用在計量心理學和生物信息統計中的算法。作為MDS算法的一種簡單的應用，若已知二維空間上n個點的兩兩距離，即完全的距離矩陣LALL(n,n)，則可以反解出這n個點的二維相對拓撲。YiShang等人[8]最早將MDS算法應用到無線網絡定位中，本文也采用了類似的思路。由于通過路由過程獲得的連接矩陣L或距離矩陣D都只是部分鏈路，所以還需要通過最短路徑算法生成在原矩陣中不連通的節點之間的近似距離，得到近似的DALL來作為MDS算法的輸入。
在獲得距離矩陣DALL之后，就可以根據MDS算法計算得到節點的相對二維拓撲分布，但該分布與真實分布存在縮放，旋轉和平移的關系。因為m個網關節點都已知自身位置，當m≥3時，可以根據網關節點的位置，對相對拓撲進行坐標變換得到最終估計的二維拓撲。
3.算法實現過程
3.1 定向擴散
目的是盡可能多的攜帶節點間的連接或測距信息，在建立梯度階段中，每個節點可以得到其下一跳節點ID。在傳輸數據階段，則將下一跳節點ID也打入數據包，按照最大梯度方向發往網關節點。當節點具有RSSI時，還要將下一跳節點對應的測距結果發往網關節點。
3.2 計算節點距離矩陣DALL
目的是提取網關數據中關于節點連接或測距的信息，并通過最短路徑算法得到所有節點間的近似距離，即完全的距離矩陣。當節點具有RSSI時，則可以根據數據包中的每個節點的測距信息生成部分距離矩陣D，然后采用Floyd最短路徑算法，生成DALL。若節點不具備RSSI，則將連通表示為單位距離1，同樣用Floyd最短路徑算法，由連接矩陣L生成DALL。
3.3 多維標度分析MDS
將節點距離矩陣DALL作為MDS算法的輸入矩陣，可以獲得節點的相對位置估計X ’, Y ’。
3.4 平移和旋轉變換
通過比對已知位置的網關節點，將MDS結果進行坐標變換使得網關位置均方誤差最小。即設X’, Y’為MDS輸出的網關節點位置，求變換矩陣A, B使得[X’’, Y’’] = A [X’, Y’] + B與網關節點已知位置[X, Y]的均方誤差最小。
4.仿真結果和分析
算法仿真采用Matlab 6.5，仿真場景為100個傳感器節點隨機均勻分布在半徑50m的圓型區域內，網絡中有大于等于三個已知位置的網關節點。
在圖2的仿真中，10個網關節點均勻分布在半徑為10米的圓周上，射頻通信距離取20m，射頻信號測距誤差為20%，圖中線段長度代表定位誤差大小。仿真結果直觀的給出了RBSL算法在節點具有RSSI和沒有RSSI情況下定位的效果。從圖2的仿真中，還可以發現RBSL算法的一個應用場景，即在大范圍的數據采集中，如果只有一個網關節點，可以通過數據采集員手持一個網關節點在一個小范圍內移動，在不同位置采集數據就可以對節點進行定位。
圖2：RBSL算法仿真結果1
圖3-a給出了節點RSSI測距誤差對結果的影響，可以發現，當測距誤差在20%以內時，定位結果較好，而若測距誤差進一步增大，則結果惡化較為明顯。圖3-b給出了節點通信距離對結果的影響，可以發現在通信距離=25m時定位誤差最低，這是因為通信距離過短會使得部分邊緣節點只有很少的鄰居，從而導致這些節點定位精度很低，而當通信距離過長時，網絡中的路由鏈路變少，導致能獲得鏈路信息變少，同樣降低了定位精度。
圖3：RBSL算法仿真結果2
5.結論和研究展望
針對無線傳感器網絡的大范圍數據采集應用場景，本文作者提出了基于路由信息的傳感器網絡定位算法RBSL。RBSL算法的主要優點是通信開銷小，只需要每個節點在自身數據包上附加幾字節的信息，且容易實現，在大范圍的數據采集場景，只需要多個網關節點或一個可移動的網關節點就可以獲得節點的定位結果。RBSL算法存在的問題是計算量較大，MDS和Floyd最短路徑算法復雜度均為O(n3)。但因在數據采集場景下，執行計算任務的是網關PC節點，因此計算量的問題相對是可以接受的。此外，在前面的分析中假設網絡均勻同構，事實上傳感器節點性能可能并不相同，且由于地形等因素影響也會造成網絡的不均勻，反映在RBSL算法中就是節點間測距結果精度的不同，如何在MDS算法中對精度不同的測距結果進行加權是下一步的研究任務之一。
作者所在的清華大學電子工程系復雜系統工程實驗室 (CESL, Complex Engineering System Lab)已經自主開發了“靈活的低成本無線傳感器網絡平臺”，即FLOWS (Flexible Low-cOst Wireless Sensor network platform)。我們正在進行FLOWS系統在智能大廈定位系統的研究與開發，相信會有很好的應用前景和經濟效益。
本文作者創新點：將傳感器網絡路由和定位信息的獲取過程結合，易于在現有系統上實現，降低了定位過程的通信開銷，并采用MDS算法獲得了較好的定位精度。