基于路由信息的傳感網(wǎng)絡(luò )定位算法

1.引言

無(wú)線(xiàn)傳感器網(wǎng)絡(luò )是近年來(lái)一個(gè)熱點(diǎn)研究領(lǐng)域，其中傳感器網(wǎng)絡(luò )定位技術(shù)也越來(lái)越受到人們的關(guān)注，這是因為傳感器網(wǎng)絡(luò )的大量應用都依賴(lài)于節點(diǎn)的位置信息，例如在戰場(chǎng)偵察、生態(tài)環(huán)境監測、地震洪水火災等現場(chǎng)的監控等應用中，都需要知道傳感器節點(diǎn)的位置信息，從而獲知信息來(lái)源的準確位置。

現有無(wú)線(xiàn)傳感器網(wǎng)絡(luò )定位系統種類(lèi)繁多，實(shí)現方法各異[1][2]。具有代表性的有采用超聲波測距的TDOA(TimeDifference of Arrival)系統[3]，基于RSSI (Receive Signal Strength Indicator)的技術(shù)[4]，基于網(wǎng)絡(luò )連通性的質(zhì)心定位算法[5]，基于多跳傳感器網(wǎng)絡(luò )節點(diǎn)間跳數的DV-Hop算法[6]等?，F有算法大多存在額外的硬件開(kāi)銷(xiāo)，或需要較多已知位置的參考節點(diǎn)，而且都有較大的通信開(kāi)銷(xiāo)，帶來(lái)了傳感器節點(diǎn)額外的功耗，這樣就降低了全網(wǎng)的生存周期。因此，需要針對無(wú)線(xiàn)傳感器網(wǎng)絡(luò )的具體場(chǎng)景，設計低成本，低開(kāi)銷(xiāo)，易實(shí)現的定位算法。

2.基于路由信息的定位算法

2.1研究場(chǎng)景定義

無(wú)線(xiàn)傳感器網(wǎng)絡(luò )的應用場(chǎng)景各異，對定位的需求也各不相同。因此，在進(jìn)行定位算法的設計前，必須選定應用場(chǎng)景進(jìn)行有針對性的設計。本文選用傳感器網(wǎng)絡(luò )中廣泛應用的大范圍數據采集場(chǎng)景，例如土壤溫濕度監測、森林火險預警、智能大廈人員數據采集等，作為研究前提。

在這種場(chǎng)景下，數量眾多的傳感器節點(diǎn)分布在較大范圍的區域內，節點(diǎn)需要通過(guò)多跳路由將數據返回到一個(gè)或多個(gè)網(wǎng)關(guān)節點(diǎn)。所有傳感器節點(diǎn)不裝配GPS、超聲收發(fā)器、有向天線(xiàn)等額外的定位和測距設備，節點(diǎn)射頻模塊只具備射頻信號強度檢測能力(RSSI)，甚至RSSI能力也不具備（即只有通信功能）。為了方便下面的研究，進(jìn)一步對場(chǎng)景作如下簡(jiǎn)化定義：

1.傳感器節點(diǎn)數目表示為n,網(wǎng)關(guān)節點(diǎn)數目表示為m；

2.n個(gè)傳感器節點(diǎn)在區域內隨機均勻分布，自身位置為(xi,yi)均未知，其中i= 1...n；

3.m個(gè)網(wǎng)關(guān)節點(diǎn)在區域內以某種規律分布，自身位置(xi,yi)均已知，其中i= n+1...n+m；

4.傳感器節點(diǎn)均以一定且相同的周期采集數據，節點(diǎn)間相對靜止；

5.節點(diǎn)采用無(wú)線(xiàn)全向天線(xiàn)進(jìn)行互通信，RSS測距的先驗概率分布滿(mǎn)足高斯分布；

2.2設計思路

而且因為數據采集任務(wù)對網(wǎng)絡(luò )的存活時(shí)間要求一般較高，所以降低傳感器節點(diǎn)的功耗，即降低傳感器節點(diǎn)的通信開(kāi)銷(xiāo)就成為設計定位算法中重要的因素。而現有定位算法存在的主要問(wèn)題就是通信開(kāi)銷(xiāo)大，其中有一個(gè)重要原因是現有的研究將定位過(guò)程與網(wǎng)絡(luò )路由和數據采集看作獨立的過(guò)程，而事實(shí)上這兩個(gè)過(guò)程存在大量通信的重復，這樣就帶來(lái)了額外的通信開(kāi)銷(xiāo)。本文的研究就是將路由協(xié)議與定位算法結合來(lái)減少這部分開(kāi)銷(xiāo)，基本思路是通過(guò)在數據包上附加網(wǎng)絡(luò )路由信息來(lái)獲得部分節點(diǎn)間的連接和距離關(guān)系，然后根據這些關(guān)系來(lái)進(jìn)行傳感器節點(diǎn)定位，該算法命名為RBSL(RoutinginformationBased Sensor Localization)。

本文選用了傳感器網(wǎng)絡(luò )中常用的定向擴散路由協(xié)議[7](DirectedDiffusion)作為研究的基礎。定向擴散路由協(xié)議是一種以數據為中心的路由協(xié)議，網(wǎng)關(guān)節點(diǎn)向所有傳感器節點(diǎn)發(fā)送對任務(wù)描述的“興趣”(Interest)，“興趣”會(huì )逐漸在全網(wǎng)中擴散，最終達到所有匹配“興趣”的傳感器節點(diǎn)，與此同時(shí)也建立起了從網(wǎng)關(guān)節點(diǎn)到傳感器節點(diǎn)的“梯度”，傳感器節點(diǎn)會(huì )沿著(zhù)梯度最大的方向將數據傳回網(wǎng)關(guān)節點(diǎn)。定向擴散的原理示意圖如下圖1所示：

對于全網(wǎng)數據采集的場(chǎng)景，網(wǎng)關(guān)節點(diǎn)發(fā)送的“興趣”是采集所有節點(diǎn)數據。在建立梯度之后，每個(gè)一個(gè)傳感器節點(diǎn)都有一個(gè)自己對網(wǎng)關(guān)節點(diǎn)的最大“梯度”方向，即下一跳傳輸的目的節點(diǎn)編號(ID)。若每個(gè)傳感器節點(diǎn)在發(fā)送數據包末尾都附加自己的下一跳節點(diǎn)ID，則在每一個(gè)網(wǎng)關(guān)節點(diǎn)就都可以獲得網(wǎng)絡(luò )中n條鏈路的連接情況，即獲得了到一個(gè)網(wǎng)關(guān)節點(diǎn)的樹(shù)狀路由表。將m個(gè)網(wǎng)關(guān)節點(diǎn)的數據進(jìn)行綜合就可以獲得更多條鏈路的連接情況。將獲得的n個(gè)傳感器節點(diǎn)和m個(gè)網(wǎng)關(guān)節點(diǎn)之間的連接關(guān)系表示為對稱(chēng)連接矩陣L(n+m,n+m)，其中Lij= 1 表示i, j節點(diǎn)存在路由鏈路，反之Lij = 0表示不存在路由鏈路，其中1≤i, j≤ n+m，若1≤i≤n表示i為傳感器節點(diǎn)，若n

進(jìn)一步的，如果傳感器節點(diǎn)具有RSSI，可以根據射頻信號傳輸的經(jīng)驗模型估計鏈路距離dij，同樣將估計距離發(fā)往網(wǎng)關(guān)節點(diǎn)。與連接矩陣L類(lèi)似可以生成對稱(chēng)距離矩陣，表示為D(n+m,n+m)，其中Dij=Dji 表示i, j節點(diǎn)間路由鏈路的估計距離。

下一步就是根據連接矩陣L或距離矩陣D來(lái)進(jìn)行節點(diǎn)定位。這里就需要用到MDS算法，MDS算法的全稱(chēng)是多維標度分析（Multi-DimensionalScaling），是一種最早應用在計量心理學(xué)和生物信息統計中的算法。作為MDS算法的一種簡(jiǎn)單的應用，若已知二維空間上n個(gè)點(diǎn)的兩兩距離，即完全的距離矩陣LALL(n,n)，則可以反解出這n個(gè)點(diǎn)的二維相對拓撲。YiShang等人[8]最早將MDS算法應用到無(wú)線(xiàn)網(wǎng)絡(luò )定位中，本文也采用了類(lèi)似的思路。由于通過(guò)路由過(guò)程獲得的連接矩陣L或距離矩陣D都只是部分鏈路，所以還需要通過(guò)最短路徑算法生成在原矩陣中不連通的節點(diǎn)之間的近似距離，得到近似的DALL來(lái)作為MDS算法的輸入。

在獲得距離矩陣DALL之后，就可以根據MDS算法計算得到節點(diǎn)的相對二維拓撲分布，但該分布與真實(shí)分布存在縮放，旋轉和平移的關(guān)系。因為m個(gè)網(wǎng)關(guān)節點(diǎn)都已知自身位置，當m≥3時(shí)，可以根據網(wǎng)關(guān)節點(diǎn)的位置，對相對拓撲進(jìn)行坐標變換得到最終估計的二維拓撲。