李松生

摘要：無(wú)線傳感器網(wǎng)絡(luò)若收集的數(shù)據(jù)帶有位置信息，則作用更加顯著，普遍應(yīng)用的GPS對(duì)能耗要求較高，但無(wú)線傳感器為了延長(zhǎng)壽命和工作時(shí)間，為能源節(jié)儉型，而且GPS成本高于傳感器，所以單個(gè)傳感器配備GPS是不可行的?？梢苿?dòng)燈塔能夠重復(fù)使用，且可以配置GPS、可充電電源，無(wú)人機(jī)是典型的可移動(dòng)燈塔的應(yīng)用實(shí)例，由算法實(shí)時(shí)決定的無(wú)人機(jī)動(dòng)態(tài)路徑是無(wú)線傳感器網(wǎng)絡(luò)定位的更優(yōu)選擇。實(shí)驗(yàn)與仿真結(jié)果表明，與傳統(tǒng)靜態(tài)路徑算法相比，該算法更加靈活，效率更高，用類似的時(shí)長(zhǎng)和距離，可實(shí)現(xiàn)平均90%的定位率。

關(guān)鍵詞：無(wú)線傳感器網(wǎng)絡(luò)；傳感器；可移動(dòng)燈塔；靜態(tài)路徑；動(dòng)態(tài)路徑；無(wú)人機(jī)

DOIDOI：10.11907/rjdk.173245

中圖分類號(hào)：TP301

文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1672-7800（2018）008-0065-06

英文摘要Abstract：Data collected by WSN is more valuable if it provides location information.GPS is the common source of location information，but it requires sustainable energy which is not available from wireless sensor，in addition，the cost of GPS is too expensive for WSN compared to the cost of sensor.Mobile beacon is a special sensor which is equipped with GPS and and it is rechargeable power supply and flexible to move.It can be alternative of many static beacons which are fixed.Static path of mobile beacon can be planted in advance so it is intentional and suitable for regular territory.By contrast，dynamic path need not know the condition and it is flexible and economical with time.UAV is popular and affordable currently，and it meets the need of mobile beacon.Simulation in the paper proves that dynamic path for localization of WSN based on UAV is effective and efficient with similar steps of static path and it can achieve 90% localized rate in average.

英文關(guān)鍵詞Key Words：WSN；sensor；mobile beacon；static path；dynamic path；UAV

0 引言

WSN由一組互聯(lián)的小尺寸、低成本傳感器組成，通常用于監(jiān)視特定區(qū)域參數(shù)[1]，其收集到的數(shù)據(jù)如果帶有位置信息將更具有價(jià)值。GPS常用于提供位置信息[2]，但其能耗較高，不適用于要求低能耗的WSN。燈塔作為WSN中的一個(gè)特殊節(jié)點(diǎn)，可配備GPS且具有高電量。可移動(dòng)的燈塔（MBC）能夠代替多個(gè)靜態(tài)燈塔，穿越監(jiān)測(cè)區(qū)域發(fā)現(xiàn)傳感器位置，從而幫助傳感器提供帶有位置信息的傳感數(shù)據(jù)。無(wú)人機(jī)（UAV）是理想的可移動(dòng)燈塔，其移動(dòng)靈活，可反復(fù)充電以保證電源充足[3]。最新的智能飛行模式[4]包括航向鎖定、航點(diǎn)飛行與興趣點(diǎn)環(huán)繞等，使UAV的控制更加靈活。更重要的是，由于無(wú)人機(jī)制造公司對(duì)API開(kāi)放，使固件層次的直接編程控制無(wú)人機(jī)成為可能。

可移動(dòng)燈塔路徑將決定傳感器定位所需時(shí)間、成功百分比及定位準(zhǔn)確性。靜態(tài)路徑，也即預(yù)先規(guī)劃好的路徑適用于傳感器均勻分布的規(guī)則區(qū)域，而動(dòng)態(tài)路徑由燈塔在運(yùn)動(dòng)過(guò)程中接收到的傳感器信息變化實(shí)時(shí)決定，更適用于傳感器不均勻分布的不規(guī)則區(qū)域。由于傳感器通常隨機(jī)分布在目標(biāo)區(qū)域，所以動(dòng)態(tài)路徑方法更加合理與可行[5]。

幾何學(xué)由于具有直觀特性，因而在路徑設(shè)計(jì)方面應(yīng)用廣泛。Xiao B[6]等提出兩種基于MB的傳感器定位方法。一種利用MB到達(dá)與離開(kāi)傳感器時(shí)可能的重疊區(qū)域（ADO），縮小傳感器的可能位置范圍；另一種根據(jù)MB越接近則信號(hào)越強(qiáng)的基本原理，利用接收到的信號(hào)強(qiáng)度（RSS）推測(cè)MB最接近的時(shí)刻。以上兩種方法都要求MB嚴(yán)格跟從預(yù)設(shè)路徑，但有些位置的傳感器仍無(wú)法定位。根據(jù)圓上任意兩點(diǎn)形成線段的垂直平分線必然通過(guò)圓心的幾何原理，如果傳感器接收到3個(gè)來(lái)自MB的信號(hào)，則可確定自身位置，即3點(diǎn)形成兩線段所在圓的圓心[7]。由于圓心位置最后由RSS推算而來(lái)，所以誤差相對(duì)較大，隨機(jī)理論與RSS配合更好。M L Sichitiu、V Ramadurai[8]提出利用貝葉斯推理處理MB收集到的傳感器數(shù)據(jù)，從而推斷傳感器位置。其通過(guò)大量測(cè)試獲得距離與RSS之間的概率密度函數(shù)（PDF），并且需要不斷校正；文獻(xiàn)[9]同樣基于貝葉斯濾波器的粒子濾波器，即在多組有加權(quán)值的隨機(jī)樣本中應(yīng)用蒙特卡洛濾波器，然后利用方差決定傳感器最終位置，樣本越多，方差越小，位置越準(zhǔn)確，計(jì)算量越大，所以該算法對(duì)MB的運(yùn)算能力要求很高；Kim K 、Lee W[10]應(yīng)用粒子濾波器，利用一臺(tái)專用電腦進(jìn)行運(yùn)算，選擇RSS與距離的相關(guān)性作為加權(quán)值，用標(biāo)準(zhǔn)差判斷位置的收斂。概率論所需計(jì)算量較大，無(wú)法適用于要求低運(yùn)算、低能耗的無(wú)線傳感器。

上述文獻(xiàn)提出的靜態(tài)路徑規(guī)劃主要應(yīng)用于水平和垂直線，R Huang、G V Zaruba提出掃描、雙掃描、Hilbert曲線幾種路徑[11]；文獻(xiàn)[12]又增加了圓和S圓兩種方式，并應(yīng)用克拉美羅界作為評(píng)估工具比較以上路徑。共線性是直線路徑中的主要問(wèn)題[13]，提高掃描分辨率可以減少共線性的影響，但導(dǎo)致路徑變長(zhǎng)。同心圓越多，覆蓋率越高，但路徑越長(zhǎng)，共線性問(wèn)題越突出。連通性是WSN的內(nèi)在特性，其意味著圖論原理也可應(yīng)用于傳感器發(fā)現(xiàn)過(guò)程[14]。D Koutsonikolas等[15]提出兩種不同算法，寬度優(yōu)先（BRF）和回溯貪婪（BTG），WSN被看成是一個(gè)無(wú)向連接圖，路徑規(guī)劃轉(zhuǎn)變?yōu)樯蓸?shù)的遍歷問(wèn)題；N Patwari等[16]提出深度優(yōu)先算法，將路徑問(wèn)題轉(zhuǎn)化成旅行推銷員問(wèn)題，并建議采用淘汰、連通支配集和最小生成樹(shù)改善算法性能。與概率論相同，圖論也存在計(jì)算復(fù)雜性問(wèn)題[17-18]。

在本文提出的算法中，可移動(dòng)燈塔UAV負(fù)責(zé)所有的分析與計(jì)算工作，每次行動(dòng)有6個(gè)可供選擇的基于幾何學(xué)的新位置，傳感器只需進(jìn)行幾次通信。圖論只應(yīng)用于局部網(wǎng)絡(luò)以避開(kāi)復(fù)雜計(jì)算。鄰居數(shù)量決定燈塔走向，位置未知且擁有最多鄰居的傳感器將成為燈塔的下一個(gè)目標(biāo)。RSS用來(lái)估計(jì)距離，位置已確定的傳感器將化身為靜態(tài)燈塔。正面與負(fù)面信息都可幫助燈塔定位傳感器，燈塔只需兩個(gè)位置信息結(jié)合自身運(yùn)動(dòng)方向即可確定傳感器位置，并且所有前序信息都被重新瀏覽，以幫助確定位置未知傳感器的位置。綜上所述，所有計(jì)算都是輕量級(jí)的比較和判斷，并且集中在MBC上。

1 算法描述

1.1 基本概念

（1）位置未知傳感器Unode，位置已知傳感器Snode。

（2）參考傳感器Rnode，Snode可以轉(zhuǎn)化成Rnode。

（3）鄰居傳感器Nnode，相互可以通信的傳感器互為鄰居。

（4）所有傳感器都有唯一、獨(dú)立的編號(hào)ID，Unode.ID表示位置未知傳感器編號(hào)。

（5）可移動(dòng)燈塔MBC為算法主角，其也一樣具有唯一、獨(dú)立的ID。

（6）覆蓋半徑R，MBC與Unode的覆蓋半徑不需要一致，但為了表達(dá)與計(jì)算方便，在不失通用性的前提下本文默認(rèn)一致。

（7）可移動(dòng)燈塔的位置PMBC，每個(gè)位置都有地址ADDR和唯一、獨(dú)立的序列號(hào)SN，SN與ID不重疊。當(dāng)前位置為CPMBC，CPMBC.SN表示當(dāng)前位置的序列號(hào)。

（8）下一個(gè)位置NPMBC，其具有6種可能性，如圖1所示。

M是MBC的當(dāng)前位置CPMBC，其坐標(biāo)為（X0，Y0），將P1～P6均分以M為原點(diǎn)、R為半徑的圓，其位置（Xn，Yn）可表示為公式（1）。

Xn=X0+Rcosπ6+n-1π3Yn=Y0+Rsinπ6+n-1π3（1）

其中，n為1～6。

目標(biāo)傳感器Tnode可幫助MBC決定NPMBC，成為Tnode的條件是傳感器能接收到MBC從CPMBC發(fā)出的信息。傳感器間通信只有hello和located兩種信息， hello信息用來(lái)確定鄰居關(guān)系，內(nèi)容是信息發(fā)送者的ID，表示為hello.ID，located信息用來(lái)通知已定位的傳感器，其內(nèi)容為被定位傳感器的ID，表示為located.ID以及地址信息located.ADDR。

無(wú)線傳感器網(wǎng)絡(luò)的定位問(wèn)題可描述為：一批位置未知傳感器{Unode}隨機(jī)分布在指定區(qū)域，可移動(dòng)燈塔MBC在該區(qū)域按指定規(guī)則行走，路過(guò)位置形成路徑{PMBC}。將盡量多的Unode轉(zhuǎn)變成Snode，Snode再轉(zhuǎn)化成Rnode，以幫助MBC定位盡可能多的傳感器，實(shí)現(xiàn)從{Unode}到{Snode}的轉(zhuǎn)變。

1.2 普通傳感器

本方法的主要執(zhí)行者是MBC，普通的位置未知傳感器只是配合MBC完成定位任務(wù)。普通傳感器的任務(wù)相對(duì)簡(jiǎn)單，分為初始化與定位兩個(gè)階段：

（1）Unode初始化階段。包括：①?gòu)V播信息hello一次；②一直接收信息，將接收到的hello.ID加入到{Nnode}；③廣播自己的ID，同時(shí)收集所有鄰居的ID。如圖2所示，Unode C的{Nnode}為{A，B，D}，F(xiàn)的為{E}。

（2）Unode定位階段。未定位傳感器定位前一直處于接收狀態(tài)，第一次收到來(lái)自MBC的hello信息，上報(bào){Nnode}，否則只回答“hello”；收到定位信息，如果是自己，則located.ID=self.ID， 完成定位，成為已定位傳感器Snode，可以充當(dāng)參考傳感器Rnode；如果located.ID∈{Nnode}，被定位的傳感器則為鄰居傳感器，轉(zhuǎn)發(fā)定位信息，通知該鄰居。

因此，傳感器端基本沒(méi)有計(jì)算，只有簡(jiǎn)單的查詢和有限的交互通信，從而節(jié)省定位所需能耗，將有限的能耗留到實(shí)際的數(shù)據(jù)檢測(cè)與傳輸過(guò)程中。相反，MBC移動(dòng)能力強(qiáng)，具有足夠電量，且計(jì)算能力強(qiáng)大，其可能是無(wú)人機(jī)UAV或機(jī)器人。為了實(shí)現(xiàn)傳感器定位算法，其需要維持至少3個(gè)數(shù)據(jù)表：①位置表{PMBC}以SN為索引，內(nèi)容為地址ADDR；②{Nnode}表記錄所有收到并響應(yīng)hello信息的鄰居傳感器ID；③傳感器信息表{INFO}以傳感器的ID作為索引。

每個(gè)傳感器項(xiàng)包括以下內(nèi)容：①ADDR：地址，被定位前為空；②{Nnode}：該傳感器的鄰居傳感器信息，主要是Nnode.ID；③{MSG}：該傳感器收到的位置信息，主要是PMBC.SN或Nnode.ID。{INFO}結(jié)構(gòu)如圖3所示。

1.3 MBC工作描述

MBC在目標(biāo)區(qū)域中移動(dòng)，其第一個(gè)步驟為“首三角”，在每個(gè)PMBC位置，它都循環(huán)執(zhí)行“新參考點(diǎn)”、“參考點(diǎn)廣播”、“兩點(diǎn)測(cè)試”幾個(gè)步驟，最后是“新目標(biāo)”和“新位置”，以確定下一位置，直到再也找不到新目標(biāo)，算法結(jié)束，MBC才停止移動(dòng)。MBC工作流程如圖4所示。

首三角是指定位過(guò)程開(kāi)始時(shí)的3個(gè)PMBC位置，它們必須形成正三角形，以保證三角形內(nèi)的所有位置未知傳感器都被定位，轉(zhuǎn)化成為參考傳感器。

1.4 新PMBC

算法描述如下：

（1）新PMBC記錄→{PMBC}

（2）廣播hello

（3）While “hello”

hello.ID→ID

If {Nnode}

新的{INFO}項(xiàng)，記錄ID，ADDR為空，{Nnode}、{MSG}為空

SN→ID.{MSG}

對(duì)于每個(gè)新的PMBC，首先一條新的PMBC記錄被加入{PMBC}中，其SN=SN+1，即在之前的SN上加1，可保證其唯一性；廣播“hello”消息，并等候Unode回應(yīng)；每收到一條Unode上報(bào)的包含{Nnode}的消息，說(shuō)明該Unode第一次收到來(lái)自MBC的信息。此時(shí)MBC在傳感器信息表{INFO}中增加一項(xiàng)，保存Unode.ID與{Nnode}，同時(shí)生成空的{MSG}，將當(dāng)前位置的SN，即CPMBC.SN放到{MSG}中；如果Unode的響應(yīng)信息中沒(méi)有{Nnode}，說(shuō)明其不是第一次收到MBC信息，MBC只需將CPMBC.SN加入到{MSG}中；通信結(jié)束，MBC執(zhí)行下一步“新參考點(diǎn)”。

1.5 新參考點(diǎn)

以ID為索引遍歷{INFO}表，如果ID.ADDR為空，傳感器位置未知，其ID.{MSG}里的SN和ID總數(shù)為3，即基數(shù)|ID.{MSG}|=3，說(shuō)明該傳感器有足夠的定位信息，使用三角測(cè)量（triangulation）[19]可以直接估算位置，并將結(jié)果存儲(chǔ)到ID.ADDR。

1.6 參考點(diǎn)廣播

其算法描述如下：

ID為索引，遍歷{INFO}

If ID.ADDR

If ID.{MSG}

清空ID.{MSG}

遍歷ID.{Nnode}里的nID

If nID∈{INFO} & nID.ADDR為空

ID→nID.{MSG}

再以ID為索引遍歷{INFO}表，如果ID.ADDR不為空，傳感器位置已知；如果ID.{MSG}不為空，說(shuō)明這是剛被定位的傳感器Snode，可以轉(zhuǎn)化成Rnode，此時(shí)清空ID.{MSG}，遍歷此ID里的{Nnode}；如果Nnode.ID在{INFO}，即Nnode.ID∈{INFO}；如果Nnode.ID.ADDR為空，該Nnode尚未定位，將自己的self.ID加入Nnode.ID.{MSG}中。

如果ID.{MSG}的內(nèi)容全為ID，沒(méi)有SN，說(shuō)明該ID的定位信息全部來(lái)自鄰居Nnode，其位置信息準(zhǔn)確性較差，將不被選為Rnode。

新參考點(diǎn)和參考點(diǎn)廣播兩個(gè)步驟循環(huán)執(zhí)行，直到?jīng)]有新參考點(diǎn)為止。

1.7 兩點(diǎn)測(cè)試

當(dāng)位置未知傳感器Unode只有兩個(gè)位置信息，其接收到兩個(gè)來(lái)自PMBC或參考傳感器Rnode的信息，根據(jù)三邊測(cè)量（trilateration）[20]，它有兩個(gè)可能位置P1和P2。兩點(diǎn)測(cè)試即分別計(jì)算P1、P2與非鄰MBC的位置{PMBC}-Unode.ID.{MSG}，以及非鄰node：{Rnode}- Unode.ID.{Nnode}。如果P1或P2與任一個(gè){PMBC}或{Rnode}的距離小于MBC的覆蓋范圍R，該位置將被否決，其它位置才是正確位置。因?yàn)樵揢node既沒(méi)有收到非鄰PMBC的信息，也不可能與那些非鄰node有鄰居關(guān)系，而有鄰居關(guān)系的node已被排除在外。

如果通過(guò)兩點(diǎn)測(cè)試產(chǎn)生新的合格Rnode，根據(jù)圖4流程所示，MBC繼續(xù)重復(fù)“新參考點(diǎn)”、“參考點(diǎn)廣播”以及“兩點(diǎn)測(cè)試”過(guò)程，直到?jīng)]有新的合格參考點(diǎn)Rnode為止。至此，MBC一個(gè)新位置PMBC的全部流程結(jié)束，開(kāi)始選擇NPMBC。

1.8 NPMBC選擇

NPMBC選擇流程如下：①根據(jù)SN.{Nnode}決定候選目標(biāo)Tnode；②根據(jù)Tnode.ID.{Nnode}的基數(shù)|ID.{Nnode}|計(jì)算候選目標(biāo)Tnode的權(quán)重W；③根據(jù)位置關(guān)系Cmn計(jì)算候選NPMBC的權(quán)重，argmax∑ni=1CmiWi最大者成為NPMBC，C如公式（2）所示。

其中m為候選位置個(gè)數(shù)|{NPMBC}|，n為候選目標(biāo)個(gè)數(shù)|{Tnode}|，只有第m個(gè)NPMBC與第n個(gè)Tnode之間距離小于R時(shí)，Cmn=1，否則為0。

如果候選NPMBC權(quán)重相同，計(jì)算候選NPMBC的凈權(quán)重w，argmax（wm）成為NPMBC。如果只有一個(gè)候選目標(biāo)，MBC直接來(lái)到離目標(biāo)最近的NPMBC即可。所有CPMBC.{Nnode}里的傳感器，如果已收到兩個(gè)以上信息，即|{MSG}|內(nèi)容基數(shù)大于等于2，其將為下一PMBC的候選目標(biāo)。因?yàn)槿绻恢梦粗獋鞲衅髦皇盏?條信息，MBC無(wú)法估計(jì)其位置，則無(wú)法向其靠近。候選目標(biāo)的選擇依據(jù)是鄰居基數(shù)W=|ID.{Nnode}|，鄰居越多，權(quán)重越大。只收到兩個(gè)地址信息，還未確定位置的Unode權(quán)重再加1，因?yàn)槠渥陨砑词俏炊ㄎ坏膫鞲衅鳌?/p>

NPMBC選擇的第一原則是不能重復(fù)。MBC先檢查P1-P6是否已記錄在{PMBC}中，否則自動(dòng)成為NPMBC的候選者。遍歷NPMBC候選者，如果其與候選目標(biāo)Tnode的距離小于覆蓋范圍R，說(shuō)明MBC如果選擇該位置，候選目標(biāo)將會(huì)接收到MBC的“hello”信息，該候選目標(biāo)的權(quán)重W則被累計(jì)到相應(yīng)NPMBC的權(quán)重中。最后如果存在唯一權(quán)值總和最大的NPMBC，其則為最終的NPMBC。如果沒(méi)有唯一的總權(quán)值占優(yōu)的NPMBC，進(jìn)一步擴(kuò)展算法則是NPMBC的凈權(quán)重w，因?yàn)镹PMBC候選目標(biāo)Tnode的ID為ID1～I(xiàn)Dn，其{Nnode}互有交集，所以凈權(quán)值w為|ID1.{Nnode}∪ID2.{Nnode}∪…∪IDn.{Nnode}|，w≤W。凈權(quán)值間的比較更加合理，但運(yùn)算較為復(fù)雜。凈權(quán)值w最大的候選NPMBC將會(huì)成為NPMBC。圖5是NPMBC選擇的直觀表示，M是CPMBC，P1-P6是6個(gè)候選NPMBC，A、B、C以及D、E各為一組候選目標(biāo)，所以P3、P6將是兩個(gè)候選NPMBC，最終選擇將由各自總權(quán)值決定。

綜上所述，算法從“首三角”開(kāi)始，保證有“新參考點(diǎn)”，其捆綁執(zhí)行“廣播參考點(diǎn)”與“兩點(diǎn)測(cè)試”，在每個(gè)PMBC，3個(gè)函數(shù)循環(huán)交替執(zhí)行直到?jīng)]有新參考點(diǎn)，然后決定新目標(biāo)和新位置，并移動(dòng)到新的PMBC，重復(fù)以上步驟，最后定位過(guò)程在沒(méi)有新目標(biāo)的情況下完成并退出。

2 仿真與分析

從100次仿真數(shù)據(jù)中隨機(jī)抽取數(shù)據(jù)得到仿真圖6。場(chǎng)景設(shè)置為：在一個(gè)60 *60 m的區(qū)域里，隨機(jī)分布60個(gè)傳感器，每個(gè)傳感器用“o”指示，其右邊有一對(duì)數(shù)據(jù)用“/”分開(kāi)，左邊是該傳感器ID，右邊是其鄰居個(gè)數(shù)|{Nnode}|。當(dāng)傳感器被定位時(shí)，在“o”中間加上“*”號(hào)，沒(méi)有“*”則表示傳感器未被定位。缺省設(shè)計(jì)MBC從研究區(qū)域的左下角開(kāi)始，圖中實(shí)線是MBC的行走軌跡，虛線是MBC在每個(gè)PMBC的信號(hào)覆蓋范圍R。在該仿真中，R=10 m，在此范圍內(nèi)的傳感器能接收到來(lái)自PMBC的“hello”信息并回應(yīng)。

由圖6可見(jiàn)，一共有17個(gè)MPBC、4個(gè)傳感器未被定位，從上至下ID分別為50、41、58和9。其中41和50互為鄰居，其位置偏遠(yuǎn)，沒(méi)有接收到PMBC的信息；50的另一個(gè)鄰居為11，其已被定位，沒(méi)有直接接收到PMBC的信息，所以不會(huì)轉(zhuǎn)化成Rnode，沒(méi)有廣播定位信息；ID為58的傳感器狀況與ID50類似；ID為9的傳感器有3個(gè)已被定位的鄰居，因而有機(jī)會(huì)被定位，但只有一個(gè)鄰居ID36直接接收來(lái)自MPBC的信息，并轉(zhuǎn)變?yōu)镽node，其它兩個(gè)鄰居26和7都沒(méi)有直接接收到MPBC的信息，盡管被定位，卻無(wú)法轉(zhuǎn)為Rnode，所以ID9只接收來(lái)自ID36的定位信息，而無(wú)法定位。

圖7呈現(xiàn)的是同一前提條件下的100次仿真結(jié)果，其顯示基本規(guī)律是MBC的行走距離越長(zhǎng)，被定位的傳感器越多。出現(xiàn)兩次3步的狀況是由于本仿真缺省從左下角開(kāi)始，如果隨機(jī)分布在此處的傳感器與其它傳感器沒(méi)有直接聯(lián)系，或者聯(lián)系較弱，MBC則無(wú)法決定NPMBC，因而停止。該狀況出現(xiàn)了兩次，說(shuō)明算法尚存在改善空間。

圖8是用一元線性回歸分析方法擬合的MBC行走距離與被定位傳感器之間的線性關(guān)系，其中“*”表示MBC行走距離對(duì)應(yīng)的被定位傳感器的數(shù)目平均值。當(dāng)PMBC個(gè)數(shù)大于18后，其結(jié)果不再符合線性，被定位的傳感器平均數(shù)量保持在55左右，超過(guò)總數(shù)的90%?？偣灿?0個(gè)未知傳感器，55個(gè)被定位已基本達(dá)到極限，因?yàn)榭傆袔讉€(gè)傳感器分布在研究區(qū)域邊緣。

3 結(jié)語(yǔ)

本文提出一種利用可移動(dòng)燈塔的動(dòng)態(tài)路徑實(shí)現(xiàn)無(wú)線傳感器網(wǎng)絡(luò)中位置未知傳感器定位的算法，無(wú)論從計(jì)算量還是能量消耗角度，都是一種輕量級(jí)算法，仿真結(jié)果也證明該算法是高效可行的。

由仿真數(shù)據(jù)可知，在某些場(chǎng)景中，移動(dòng)燈塔只移動(dòng)幾次即停止，被發(fā)現(xiàn)的傳感器數(shù)目也相對(duì)較少。出現(xiàn)該狀況的主要原因是算法以鄰居數(shù)目|{Nnode}|為驅(qū)動(dòng)，如果出現(xiàn)如圖6所示ID為41的傳感器狀況，其沒(méi)有鄰居，移動(dòng)燈塔則會(huì)出現(xiàn)停止的情況。改進(jìn)方法為讓移動(dòng)燈塔多移動(dòng)一步，則可能發(fā)現(xiàn)新目標(biāo)，或者換一個(gè)起點(diǎn)。缺省狀況是從左下角起步，如果出現(xiàn)突然停止而定位率低的情況，可以移動(dòng)到右下角或從其它角落開(kāi)始。

從提高效率的角度考慮，還可以嘗試的方法包括改善目標(biāo)權(quán)重，目前是所有鄰居都計(jì)算在內(nèi)，可以考慮剔除重復(fù)與已定位的鄰居，專注于尋找尚未定位的傳感器。還可縮小下一燈塔位置的選擇范圍，目前的原則是不重復(fù)，將來(lái)可以適當(dāng)降低到達(dá)位置附近的位置權(quán)重，因?yàn)樗鼈兛赡芤延凶銐虻亩ㄎ恍畔?。如果不考慮距離，優(yōu)先考慮定位率，燈塔按照靜態(tài)路徑行走將可能提高定位率。

隨著無(wú)人機(jī)技術(shù)的不斷成熟與廣泛應(yīng)用[21-22]，該算法的現(xiàn)實(shí)意義是無(wú)人機(jī)可以充當(dāng)移動(dòng)燈塔，只要把該算法植入無(wú)人機(jī)的飛行控制系統(tǒng)，即可實(shí)現(xiàn)自動(dòng)尋找待定位的無(wú)線傳感器，發(fā)現(xiàn)與記錄傳感器位置，并在未來(lái)的應(yīng)用數(shù)據(jù)中附加上位置信息，以確保數(shù)據(jù)的完整性和準(zhǔn)確性。

參考文獻(xiàn)：

[1] 崔莉，鞠海玲，苗勇，等.無(wú)線傳感器網(wǎng)絡(luò)研究進(jìn)展[J].計(jì)算機(jī)研究與發(fā)展， 2005，42（1）：163-174.

[2] 彭宇，王丹.無(wú)線傳感器網(wǎng)絡(luò)定位技術(shù)綜述[J].電子測(cè)量與儀器學(xué)報(bào)，2011，25（5）：389-399.

[3] 畢凱，李英成，丁曉波，等.輕小型無(wú)人機(jī)航攝技術(shù)現(xiàn)狀及發(fā)展趨勢(shì)[J].測(cè)繪通報(bào)，2015（3）：27-31，48.

[4] 大疆.智能飛行新時(shí)代已經(jīng)到來(lái)[EB/OL].Http：//www.dji.com/cn/intelligent-flight-mode/v1-doc.

[5] 王成群.基于學(xué)習(xí)算法的無(wú)線傳感器網(wǎng)絡(luò)定位問(wèn)題研究[D].杭州：浙江大學(xué)，2009.

[6] XIAO B，CHEN H K，ZHOU S G.A walking beacon-assisted localization in wireless sensor networks[C].In International Conference on Communications，Glasgow，Scotland，2007：3070-3075.

[7] SSU K，OU C ，JIAU H.Localization with mobile anchor points in wireless sensor networks[J].IEEE Transactions on Vehicular Technology，2005，54 （3）：1187-1197.

[8] M L SICHITIU，V RAMADURAI.Localization of wireless sensor networks with a mobile beacon[C].In Proceedings of the 1st IEEE International Conference on Mobile Ad Hoc and Sensor Systems （MASS 2004），2004：174-183.

[9] HUANG R，ZRUBA G V.Monte carlo localization of wireless sensor networks with a single mobile beacon[J].Wirel.Netw，2008.

[10] KIM K，LEE W.MBAL：a mobile beacon-assisted localization scheme for wireless sensor networks[C].In Proc.ICCCN，2007：57-62.

[11] R HUANG，G V ZARUBA.Static path planning for mobile beacons to localize sensor networks[C].Pervasive Computing and Communications Workshops，PerCom Workshops 07.Fifth Annual IEEE International Conference on，2007：323-330.

[12] CABALLERO F，L MERINO，et al.A probabilistic framework for entire WSN localization using a mobile robot[J].Robot.Auton.Syst，2008，56（10）：798-806.

[13] 王成群.基于學(xué)習(xí)算法的無(wú)線傳感器網(wǎng)絡(luò)定位問(wèn)題研究[D].杭州：浙江大學(xué)，2009.

[14] 戴歡.無(wú)線傳感器網(wǎng)絡(luò)定位算法及其應(yīng)用研究[D].無(wú)錫：江南大學(xué)，2012.

[15] D KOUTSONIKOLAS，S M DAS，Y C HU.Path planning of mobile landmarks for localization in wireless sensor networks[C].In Proc.of IEEE Distributed Computing Systems Workshops，2006：86.

[16] N PATWARI，A HERO，J ASH，et al.Locating the nodes：cooperative geolocation of wireless sensors[J].IEEE Signal Processing Magazine，2005，22：54-69.

[17] HONGJUN LI，JIANWEN WANG，XUN LI，et al.Real-time path planning of mobile anchor node in localization for wireless sensor networks[C].Proceedings of Information and Automation，2008.

[18] X LI，N MITTON，I RYL，et al.A novel sensor localization scheme by mobile actors[C].In Proceedings of the 10th ACM International Symposium on Mobile Ad Hoc Networking and Computing （MobiHoc），2009：339-340.

[19] 王福豹，史龍，任豐原.無(wú)線傳感器網(wǎng)絡(luò)中的自身定位系統(tǒng)和算法[J].軟件學(xué)報(bào)，2005，16（5）：857-868.

[20] 杜存功，丁恩杰，苗曙光，等.無(wú)線傳感器網(wǎng)絡(luò)改進(jìn)型節(jié)點(diǎn)定位算法的研究[J].傳感器與微系統(tǒng)，2010，29（1）：52-54.

[21] 馮家莉，劉凱，朱遠(yuǎn)輝，等.無(wú)人機(jī)遙感在紅樹(shù)林資源調(diào)查中的應(yīng)用[J].熱帶地理，2015，35（1）：35-42.

[22] 張波，羅錫文，蘭玉彬，等.基于無(wú)線傳感器網(wǎng)絡(luò)的無(wú)人機(jī)農(nóng)田信息監(jiān)測(cè)系統(tǒng)[J].農(nóng)業(yè)工程學(xué)報(bào)，2015，31（17）：176-182.

（責(zé)任編輯：黃 ?。?/p>