1.引言

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

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

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

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

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

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

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

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

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

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

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

2.2設(shè)計(jì)思路

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

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

圖1：定向擴(kuò)散路由原理示意圖

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

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

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

在獲得距離矩陣DALL之后，就可以根據(jù)MDS算法計(jì)算得到節(jié)點(diǎn)的相對(duì)二維拓?fù)浞植?，但該分布與真實(shí)分布存在縮放，旋轉(zhuǎn)和平移的關(guān)系。因?yàn)閙個(gè)網(wǎng)關(guān)節(jié)點(diǎn)都已知自身位置，當(dāng)m≥3時(shí)，可以根據(jù)網(wǎng)關(guān)節(jié)點(diǎn)的位置，對(duì)相對(duì)拓?fù)溥M(jìn)行坐標(biāo)變換得到最終估計(jì)的二維拓?fù)洹?/span>

3.算法實(shí)現(xiàn)過(guò)程

3.1 定向擴(kuò)散

目的是盡可能多的攜帶節(jié)點(diǎn)間的連接或測(cè)距信息，在建立梯度階段中，每個(gè)節(jié)點(diǎn)可以得到其下一跳節(jié)點(diǎn)ID。在傳輸數(shù)據(jù)階段，則將下一跳節(jié)點(diǎn)ID也打入數(shù)據(jù)包，按照最大梯度方向發(fā)往網(wǎng)關(guān)節(jié)點(diǎn)。當(dāng)節(jié)點(diǎn)具有RSSI時(shí)，還要將下一跳節(jié)點(diǎn)對(duì)應(yīng)的測(cè)距結(jié)果發(fā)往網(wǎng)關(guān)節(jié)點(diǎn)。

3.2 計(jì)算節(jié)點(diǎn)距離矩陣DALL

目的是提取網(wǎng)關(guān)數(shù)據(jù)中關(guān)于節(jié)點(diǎn)連接或測(cè)距的信息，并通過(guò)最短路徑算法得到所有節(jié)點(diǎn)間的近似距離，即完全的距離矩陣。當(dāng)節(jié)點(diǎn)具有RSSI時(shí)，則可以根據(jù)數(shù)據(jù)包中的每個(gè)節(jié)點(diǎn)的測(cè)距信息生成部分距離矩陣D，然后采用Floyd最短路徑算法，生成DALL。若節(jié)點(diǎn)不具備RSSI，則將連通表示為單位距離1，同樣用Floyd最短路徑算法，由連接矩陣L生成DALL。

3.3 多維標(biāo)度分析MDS

將節(jié)點(diǎn)距離矩陣DALL作為MDS算法的輸入矩陣，可以獲得節(jié)點(diǎn)的相對(duì)位置估計(jì)X ’, Y ’。

3.4 平移和旋轉(zhuǎn)變換

通過(guò)比對(duì)已知位置的網(wǎng)關(guān)節(jié)點(diǎn)，將MDS結(jié)果進(jìn)行坐標(biāo)變換使得網(wǎng)關(guān)位置均方誤差最小。即設(shè)X’, Y’為MDS輸出的網(wǎng)關(guān)節(jié)點(diǎn)位置，求變換矩陣A, B使得[X’’, Y’’] = A [X’, Y’] + B與網(wǎng)關(guān)節(jié)點(diǎn)已知位置[X, Y]的均方誤差最小。

4.仿真結(jié)果和分析

算法仿真采用Matlab 6.5，仿真場(chǎng)景為100個(gè)傳感器節(jié)點(diǎn)隨機(jī)均勻分布在半徑50m的圓型區(qū)域內(nèi)，網(wǎng)絡(luò)中有大于等于三個(gè)已知位置的網(wǎng)關(guān)節(jié)點(diǎn)。

在圖2的仿真中，10個(gè)網(wǎng)關(guān)節(jié)點(diǎn)均勻分布在半徑為10米的圓周上，射頻通信距離取20m，射頻信號(hào)測(cè)距誤差為20%，圖中線段長(zhǎng)度代表定位誤差大小。仿真結(jié)果直觀的給出了RBSL算法在節(jié)點(diǎn)具有RSSI和沒(méi)有RSSI情況下定位的效果。從圖2的仿真中，還可以發(fā)現(xiàn)RBSL算法的一個(gè)應(yīng)用場(chǎng)景，即在大范圍的數(shù)據(jù)采集中，如果只有一個(gè)網(wǎng)關(guān)節(jié)點(diǎn)，可以通過(guò)數(shù)據(jù)采集員手持一個(gè)網(wǎng)關(guān)節(jié)點(diǎn)在一個(gè)小范圍內(nèi)移動(dòng)，在不同位置采集數(shù)據(jù)就可以對(duì)節(jié)點(diǎn)進(jìn)行定位。

圖2：RBSL算法仿真結(jié)果1

圖3-a給出了節(jié)點(diǎn)RSSI測(cè)距誤差對(duì)結(jié)果的影響，可以發(fā)現(xiàn)，當(dāng)測(cè)距誤差在20%以內(nèi)時(shí)，定位結(jié)果較好，而若測(cè)距誤差進(jìn)一步增大，則結(jié)果惡化較為明顯。圖3-b給出了節(jié)點(diǎn)通信距離對(duì)結(jié)果的影響，可以發(fā)現(xiàn)在通信距離=25m時(shí)定位誤差最低，這是因?yàn)橥ㄐ啪嚯x過(guò)短會(huì)使得部分邊緣節(jié)點(diǎn)只有很少的鄰居，從而導(dǎo)致這些節(jié)點(diǎn)定位精度很低，而當(dāng)通信距離過(guò)長(zhǎng)時(shí)，網(wǎng)絡(luò)中的路由鏈路變少，導(dǎo)致能獲得鏈路信息變少，同樣降低了定位精度。

圖3：RBSL算法仿真結(jié)果2

5.結(jié)論和研究展望

針對(duì)無(wú)線傳感器網(wǎng)絡(luò)的大范圍數(shù)據(jù)采集應(yīng)用場(chǎng)景，本文作者提出了基于路由信息的傳感器網(wǎng)絡(luò)定位算法RBSL。RBSL算法的主要優(yōu)點(diǎn)是通信開(kāi)銷(xiāo)小，只需要每個(gè)節(jié)點(diǎn)在自身數(shù)據(jù)包上附加幾字節(jié)的信息，且容易實(shí)現(xiàn)，在大范圍的數(shù)據(jù)采集場(chǎng)景，只需要多個(gè)網(wǎng)關(guān)節(jié)點(diǎn)或一個(gè)可移動(dòng)的網(wǎng)關(guān)節(jié)點(diǎn)就可以獲得節(jié)點(diǎn)的定位結(jié)果。RBSL算法存在的問(wèn)題是計(jì)算量較大，MDS和Floyd最短路徑算法復(fù)雜度均為O(n3)。但因在數(shù)據(jù)采集場(chǎng)景下，執(zhí)行計(jì)算任務(wù)的是網(wǎng)關(guān)PC節(jié)點(diǎn)，因此計(jì)算量的問(wèn)題相對(duì)是可以接受的。此外，在前面的分析中假設(shè)網(wǎng)絡(luò)均勻同構(gòu)，事實(shí)上傳感器節(jié)點(diǎn)性能可能并不相同，且由于地形等因素影響也會(huì)造成網(wǎng)絡(luò)的不均勻，反映在RBSL算法中就是節(jié)點(diǎn)間測(cè)距結(jié)果精度的不同，如何在MDS算法中對(duì)精度不同的測(cè)距結(jié)果進(jìn)行加權(quán)是下一步的研究任務(wù)之一。

作者所在的清華大學(xué)電子工程系復(fù)雜系統(tǒng)工程實(shí)驗(yàn)室 (CESL, Complex Engineering System Lab)已經(jīng)自主開(kāi)發(fā)了“靈活的低成本無(wú)線傳感器網(wǎng)絡(luò)平臺(tái)”，即FLOWS (Flexible Low-cOst Wireless Sensor network platform)。我們正在進(jìn)行FLOWS系統(tǒng)在智能大廈定位系統(tǒng)的研究與開(kāi)發(fā)，相信會(huì)有很好的應(yīng)用前景和經(jīng)濟(jì)效益。

本文作者創(chuàng)新點(diǎn)：將傳感器網(wǎng)絡(luò)路由和定位信息的獲取過(guò)程結(jié)合，易于在現(xiàn)有系統(tǒng)上實(shí)現(xiàn)，降低了定位過(guò)程的通信開(kāi)銷(xiāo)，并采用MDS算法獲得了較好的定位精度。