基于局部信息的移動(dòng)感知網(wǎng)覆蓋方法

摘 要：移動(dòng)感知網(wǎng)是一個(gè)由許多帶有傳感器的自主移動(dòng)機(jī)器人組成的分布式傳感器網(wǎng)絡(luò)。為了更好地部署這些移動(dòng)機(jī)器人節(jié)點(diǎn)，形成最大化覆蓋感知區(qū)域，提出了一種基于機(jī)器人局部信息的分布式感知網(wǎng)覆蓋方法。每個(gè)節(jié)點(diǎn)利用與鄰居節(jié)點(diǎn)之間的虛擬人工勢(shì)場(chǎng)產(chǎn)生的虛擬作用力來(lái)控制移動(dòng)節(jié)點(diǎn)的運(yùn)動(dòng)和節(jié)點(diǎn)間的避碰，使移動(dòng)節(jié)點(diǎn)能夠在允許的時(shí)間內(nèi)，以較少的能量消耗移動(dòng)到各自理想的位置。采用李亞普諾夫函數(shù)進(jìn)行了感知網(wǎng)節(jié)點(diǎn)勢(shì)場(chǎng)梯度的理論分析，用計(jì)算機(jī)仿真實(shí)驗(yàn)驗(yàn)證了該方法的有效性，并與模擬退火算法進(jìn)行了性能比較。

關(guān)鍵詞：移動(dòng)感知網(wǎng)；覆蓋；虛擬力；多機(jī)器人；避碰

中圖分類號(hào)：TP242．6 文獻(xiàn)標(biāo)志碼：A

文章編號(hào)：1001-3695(2008)07-2016-04



Coverage of mobile sensor networks based on local information

ZHOU Tong1，3， HONG Bingrong1， PIAO Songhao1， ZHOU Hongyu2

(1.School of Computer Science Technology， Harbin Institute of Technology， Harbin 150001， China；2.School of Mechanical Power Engineering， Harbin University of Science Technology， Harbin 150080， China；3.Heilongjiang Institute of Metrology， Harbin 150036， China)Abstract:Mobile sensor network is a distributed sensor networks which is composed of many autonomous mobile robots with sensors.Presented a new distributed coverage method of mobile robot nodes based local information in order to deploy these nodes for forming maximum coverage of sensing area. Utilised the forces resulted from virtual potential fields between these nodes to control the movement of mobile nodes and collision avoidance. By this way mobile nodes moved to each perfect position using a little energy consume in allowable time.Made theoretic analysis of mobile sensor networks potential gradient was made by Lyapunov function. Numeric simulation verified the valid of the method and compared the performance with simulated anneal algorithm. 

Key words:mobile sensor networks; coverage; virtual force; multirobot; collision avoidance

0 引言

感知網(wǎng)的首要任務(wù)就是感知環(huán)境，傳送感知數(shù)據(jù)，并進(jìn)行進(jìn)一步的處理^[1]。傳感器部署的好壞直接影響感知網(wǎng)的感知區(qū)域覆蓋性能。覆蓋問(wèn)題是指區(qū)域覆蓋^[2]，它可被看做是系統(tǒng)服務(wù)質(zhì)量的一個(gè)測(cè)量標(biāo)準(zhǔn)，當(dāng)覆蓋率下降到一定閾值，感知網(wǎng)將不能正常發(fā)揮作用^[3]。 在大多數(shù)感知網(wǎng)的研究中，感知網(wǎng)使用的只是靜態(tài)節(jié)點(diǎn)^[4]，這種節(jié)點(diǎn)沒(méi)有移動(dòng)功能，對(duì)感知網(wǎng)的魯棒性、容錯(cuò)等有很大的限制。移動(dòng)感知網(wǎng)是一個(gè)動(dòng)態(tài)系統(tǒng)，能夠協(xié)作地實(shí)時(shí)監(jiān)測(cè)、感知和采集各種環(huán)境或監(jiān)測(cè)對(duì)象的信息，并對(duì)其進(jìn)行處理，傳送這些信息到用戶。在部署移動(dòng)傳感器節(jié)點(diǎn)方面已有許多研究，但它們大多數(shù)是基于集中式控制方法^[5，6]，然而在許多傳感器部署環(huán)境中，由于網(wǎng)絡(luò)分割很難組織成傳感器集群，使用一個(gè)中心服務(wù)器進(jìn)行控制是不可行的，而且容易由于單個(gè)節(jié)點(diǎn)的失效而失敗，使用移動(dòng)傳感器來(lái)幫助部署節(jié)點(diǎn)可以避免這個(gè)問(wèn)題^[7]。在本文中，給作為節(jié)點(diǎn)的移動(dòng)機(jī)器人裝備一些傳感器，組成一種移動(dòng)感知網(wǎng)的形式，既考慮了感知網(wǎng)節(jié)點(diǎn)的重構(gòu)，具有自適應(yīng)功能，又能提高感知網(wǎng)的覆蓋性能。這種節(jié)點(diǎn)覆蓋方法是一種分布式方法，也是一種啟發(fā)式方法，無(wú)須集中控制，而且算法簡(jiǎn)單、易操作，理論分析和仿真實(shí)驗(yàn)均驗(yàn)證了其可行性和高效性。 

1 問(wèn)題描述

在一個(gè)面積為L×L柵格的二維正方形無(wú)障礙感知區(qū)域內(nèi)，隨機(jī)地分布著n個(gè)可移動(dòng)的傳感器（自主移動(dòng)機(jī)器人），它們共同組成一個(gè)移動(dòng)傳感器網(wǎng)絡(luò)，由于部署時(shí)的隨機(jī)性，使網(wǎng)絡(luò)的覆蓋率沒(méi)有達(dá)到預(yù)期的要求，這時(shí)n個(gè)移動(dòng)節(jié)點(diǎn)將進(jìn)行重新部署。本文的目的就是尋找一種快速可行的多移動(dòng)機(jī)器人協(xié)調(diào)運(yùn)動(dòng)控制算法，使整個(gè)網(wǎng)絡(luò)的覆蓋率最大，同時(shí)移動(dòng)機(jī)器人不能躍出所給定的邊界，并且移動(dòng)節(jié)點(diǎn)所消耗的能量最低，用的時(shí)間最短。

假定移動(dòng)機(jī)器人在二維平面U內(nèi)運(yùn)動(dòng)，U={(x，y)T|x，y∈R}。其中：點(diǎn)q=(x，y)T為列向量形式；R代表全體實(shí)數(shù)集，U表示U的邊界。qi=(xi，yi)表示第i個(gè)移動(dòng)機(jī)器人的坐標(biāo)位置，i=0，1，2，…，n，qi∈R2。第i個(gè)機(jī)器人的驅(qū)動(dòng)控制力用ui∈R2表示，i=0，1，2，…，n。

q¨i=ui(1)

由于機(jī)器人的傳感器和通信裝置的功能局限性，它的感知和通信范圍是有限的，每個(gè)機(jī)器人的感知半徑為sr，通信半徑為cr。

定義1 如果兩個(gè)機(jī)器人i， j，且i≠j，兩節(jié)點(diǎn)間的歐幾里得距離小于等于cr，

qij=‖qi-qj‖≤cr(2)

則這兩個(gè)節(jié)點(diǎn)為鄰居節(jié)點(diǎn)。

一個(gè)移動(dòng)感知網(wǎng)的性能可以用感知區(qū)域的覆蓋率、節(jié)點(diǎn)分布的均勻性、節(jié)點(diǎn)覆蓋所需時(shí)間和節(jié)點(diǎn)移動(dòng)的總距離來(lái)評(píng)價(jià)。

定義2 覆蓋率是所有機(jī)器人能夠感知的區(qū)域之和與待感知區(qū)域之比，可以用下式計(jì)算:

coverage=(∪i=1，…，nSi)/S(3)

其中：Si是節(jié)點(diǎn)i覆蓋的區(qū)域面積；S是感知區(qū)域總面積；n是總節(jié)點(diǎn)數(shù)。

定義3 節(jié)點(diǎn)分布均勻性用下式計(jì)算:

其中：n是節(jié)點(diǎn)數(shù)；ki是第i個(gè)節(jié)點(diǎn)的鄰居節(jié)點(diǎn)數(shù)；Di=(ki+1)/(π(cr)2)是第i個(gè)節(jié)點(diǎn)的局部密度；Da=n/L2是節(jié)點(diǎn)的平均密度。Uniformity越小越好，也就表示節(jié)點(diǎn)的分布更均勻。

定義4 運(yùn)行時(shí)間time是感知網(wǎng)節(jié)點(diǎn)部署后達(dá)到穩(wěn)定狀態(tài)時(shí)所耗費(fèi)的總時(shí)間，此時(shí)間應(yīng)盡量短。在用計(jì)算機(jī)仿真時(shí)，就是程序所運(yùn)行的迭代步數(shù)。

定義5 移動(dòng)距離distance是所有移動(dòng)節(jié)點(diǎn)移動(dòng)的總距離。由于節(jié)點(diǎn)是由移動(dòng)機(jī)器人組成，由電池供電的機(jī)器人應(yīng)該移動(dòng)最短距離達(dá)到預(yù)定位置，這也是一個(gè)評(píng)價(jià)感知網(wǎng)標(biāo)準(zhǔn)的重要指標(biāo)。所有移動(dòng)節(jié)點(diǎn)運(yùn)行的總距離可以用下式計(jì)算:

distance=tmaxt=1ni=1di(t)(5)

其中：tmax是感知網(wǎng)運(yùn)行的總迭代步數(shù)；di是每個(gè)移動(dòng)節(jié)點(diǎn)在每次運(yùn)動(dòng)中的移動(dòng)距離。

2 節(jié)點(diǎn)覆蓋方法

2．1 虛擬力

人工勢(shì)場(chǎng)法被廣泛用于移動(dòng)機(jī)器人的局部導(dǎo)航、避障、隊(duì)形控制和感知網(wǎng)的節(jié)點(diǎn)覆蓋^[8~10]。在本文中，把人工勢(shì)場(chǎng)法用于移動(dòng)節(jié)點(diǎn)的覆蓋問(wèn)題，這種方法模擬了電子勢(shì)場(chǎng)的概念，如果假設(shè)感知網(wǎng)中的每個(gè)節(jié)點(diǎn)都攜帶一個(gè)正電荷，就可以定義一個(gè)可量測(cè)的勢(shì)場(chǎng)，每個(gè)節(jié)點(diǎn)受到感知網(wǎng)中其他節(jié)點(diǎn)的排斥，這種排斥力使整個(gè)網(wǎng)絡(luò)中的所有移動(dòng)節(jié)點(diǎn)向感知網(wǎng)中的其他地域擴(kuò)散，最終達(dá)到平衡狀態(tài)，也就是達(dá)到了感知區(qū)域的最大覆蓋狀態(tài)。

在此引入兩種虛擬勢(shì)場(chǎng)力， 第i個(gè)機(jī)器人與它的有鄰居節(jié)點(diǎn)關(guān)系機(jī)器人之間的作用力為

其中：mi是第i個(gè)機(jī)器人的鄰居機(jī)器人總數(shù)；kR>0，是一個(gè)增益系數(shù)。D∈U，if dmin(qi-D)



其中：kB>0，是一個(gè)增益系數(shù)。qi受到qj的排斥力是它所處勢(shì)場(chǎng)的負(fù)梯度：

qi受到qj的排斥力與qj受到qi的排斥力是作用力與反作用力的關(guān)系，即

且有

其中：kd>0，是一個(gè)阻尼項(xiàng)。

使用李亞普諾夫函數(shù)作為系統(tǒng)內(nèi)所有動(dòng)能和勢(shì)能之和：

系統(tǒng)在沒(méi)有外力的作用下，保證系統(tǒng)最終穩(wěn)定的條件是所有機(jī)器人所受的合力為0，即

2．2 節(jié)點(diǎn)勢(shì)場(chǎng)梯度分析

在多機(jī)器人網(wǎng)絡(luò)中，每個(gè)機(jī)器人可以在它的通信范圍內(nèi)收到其他機(jī)器人的位置信息，也可以在感知范圍內(nèi)感知到障礙物的位置信息。通過(guò)這些節(jié)點(diǎn)和障礙物的位置信息構(gòu)成了此機(jī)器人的勢(shì)場(chǎng)，所有機(jī)器人的勢(shì)場(chǎng)之和就構(gòu)成了感知網(wǎng)的勢(shì)場(chǎng)分布。

對(duì)于一個(gè)單獨(dú)的機(jī)器人，q¨i=ui，同時(shí)定義控制規(guī)則為

其中：T:R2→R為梯度勢(shì)場(chǎng)；kd＞0；η是一個(gè)常量控制參數(shù)。如果機(jī)器人在勢(shì)場(chǎng)的原點(diǎn)則梯度勢(shì)場(chǎng)T(qi)存在極小值。使用下面形式的李亞普諾夫函數(shù)容易證明在原點(diǎn)的漸近穩(wěn)定性：

V(qi，i)=i×i/2+ηT(qi)(16)

其中η＞0。如果原點(diǎn)是惟一的，并且全局極小，那么全局漸近穩(wěn)定性是存在的。

如果對(duì)一組機(jī)器人中的每個(gè)機(jī)器人使用同樣的控制規(guī)則，并且加入機(jī)器人之間的相互作用力，可得到下面的運(yùn)動(dòng)學(xué)方程:

q¨i=-kdi-ηΔT(qi)-mij=0FR(qij)(17)

其中：mi是第i個(gè)機(jī)器人在通信半徑范圍內(nèi)所有鄰居機(jī)器人數(shù)目之和。因?yàn)橛瑟玭個(gè)機(jī)器人組成的系統(tǒng)沒(méi)有受到外力作用，可以用李亞普諾夫函數(shù)作為表示系統(tǒng)的動(dòng)能和勢(shì)能之和，而且在勢(shì)能中還包括勢(shì)場(chǎng)T的勢(shì)能:

微分方程為

把式(17)代入(19)得到

命題1 如果T是一個(gè)勢(shì)場(chǎng)函數(shù)，并且考慮一組機(jī)器人具有式(17)規(guī)定的控制規(guī)則，那么機(jī)器人系統(tǒng)將會(huì)達(dá)到一個(gè)穩(wěn)定的平衡狀態(tài)。

證明 基于控制動(dòng)力學(xué)的對(duì)稱性，應(yīng)用LaSalle的不變性原理可以得出非孤立的平衡狀態(tài)集合具有收斂性，所有機(jī)器人相互間作用的勢(shì)場(chǎng)與環(huán)境勢(shì)場(chǎng)之和的極小值可以通過(guò)解式(17)來(lái)得到，此時(shí)q¨i=i=0，則式(17)為

由FR(qij)=-FR(qij)得到ni=1ΔT(qi)=0。因此只要所有機(jī)器人所受的環(huán)境勢(shì)場(chǎng)梯度之和為0，系統(tǒng)就能達(dá)到穩(wěn)定狀態(tài)。 證畢。

命題2 假設(shè)T是一個(gè)徑向?qū)ΨQ梯度勢(shì)場(chǎng)，T=T(‖q‖)，在q=0有嚴(yán)格的全局極小值，T(‖q‖)是嚴(yán)格增加。例如對(duì)于所有的‖q‖＞0，T(‖q‖)/‖q‖＞0，那么對(duì)于具有式(17)能夠形成具有穩(wěn)定凸形外殼隊(duì)形的n個(gè)機(jī)器人，所形成的勢(shì)場(chǎng)極小值在q=0處。

證明 對(duì)于一個(gè)給定的勢(shì)場(chǎng)T，穩(wěn)定條件ni=1ΔT(qi)=0是指ni=1ai(‖qi‖)qi=0，且對(duì)于‖q‖＞0，ai＞0。如果對(duì)于某些i，qi=0，那么在機(jī)器人位置形成的凸形外殼中q=0是平凡解，所以考慮在i，qi≠0的情況。讓a=a1+…+an＞0，且bi=ai/a，那么b1+…+bn=1，所以ni=1bi(‖qi‖)qi=0，極小值在穩(wěn)定狀態(tài)的凸形外殼內(nèi)。證畢。

2．3 移動(dòng)感知網(wǎng)覆蓋算法

移動(dòng)感知網(wǎng)的覆蓋主要是移動(dòng)節(jié)點(diǎn)的部署。因?yàn)楣?jié)點(diǎn)通常是隨機(jī)部署的，通過(guò)節(jié)點(diǎn)的再部署可以達(dá)到節(jié)點(diǎn)分布的均勻性。因此，每個(gè)移動(dòng)節(jié)點(diǎn)的運(yùn)動(dòng)只受當(dāng)前位置的影響，每個(gè)移動(dòng)節(jié)點(diǎn)都能適應(yīng)環(huán)境的變化以自主移動(dòng)的方式變化位置，以便能最大化感知網(wǎng)的覆蓋率和節(jié)點(diǎn)的均勻性。

每個(gè)移動(dòng)節(jié)點(diǎn)都執(zhí)行相同的算法，并且節(jié)點(diǎn)的移動(dòng)是并行同步進(jìn)行的。在每一次移動(dòng)過(guò)程中，首先移動(dòng)節(jié)點(diǎn)發(fā)送自己的位置坐標(biāo)，并要求收到信息的所有節(jié)點(diǎn)回答自己的當(dāng)前位置坐標(biāo)，接收到這些信息后，按照相對(duì)位置計(jì)算所受的作用力，同時(shí)移動(dòng)節(jié)點(diǎn)進(jìn)行邊界的感知，也按照和邊界的相對(duì)位置計(jì)算所受的作用力，這樣就可以得到每個(gè)移動(dòng)節(jié)點(diǎn)所受的合力。根據(jù)運(yùn)動(dòng)學(xué)方程，移動(dòng)節(jié)點(diǎn)運(yùn)動(dòng)到新位置，重復(fù)這個(gè)過(guò)程直到循環(huán)結(jié)束。

移動(dòng)感知網(wǎng)覆蓋算法（mobile sensornetwork coverage algorithm，MSCA）描述如下:

a)Initialize

input qi0;讀入第i個(gè)移動(dòng)節(jié)點(diǎn)的初始位置坐標(biāo);

set sr;設(shè)置移動(dòng)節(jié)點(diǎn)感知半徑;

set cr;設(shè)置移動(dòng)節(jié)點(diǎn)通信半徑;

set t＝0;設(shè)置循環(huán)變量;

set tmax;設(shè)置最大循環(huán)次數(shù);

while(t

b)Calculate virtual forces

移動(dòng)節(jié)點(diǎn)所受虛擬力計(jì)算send(request，qi(t));在通信半徑cr范圍內(nèi)對(duì)其他所有節(jié)點(diǎn)發(fā)送（回答請(qǐng)求，qi(t)）;

receive (reponse，qj);接收在cr范圍內(nèi)的所有移動(dòng)節(jié)點(diǎn)的（回應(yīng)，qj）;

根據(jù)式(6)計(jì)算FRi;

detection;在感知半徑sr范圍內(nèi)探測(cè)邊界障礙;

根據(jù)式(7)計(jì)算FBi;

計(jì)算Fi=FRi+FBi

c)Node move按照所受虛擬力進(jìn)行移動(dòng)

根據(jù)式(10)計(jì)算移動(dòng)節(jié)點(diǎn)移動(dòng)到qi(t＋1)位置，如果新位置在感知區(qū)域外，則停留在最近的邊界線上;

d)t=t+1;}

程序結(jié)束。

節(jié)點(diǎn)受到排斥力進(jìn)行移動(dòng)時(shí)，它不僅受運(yùn)動(dòng)學(xué)方程的限制，同時(shí)受到動(dòng)力學(xué)方程的約束限制，在每個(gè)時(shí)間步長(zhǎng)，即使受到的力很大，也只能按照動(dòng)力學(xué)方程允許的最大移動(dòng)距離移動(dòng)。在仿真中，假設(shè)如果移動(dòng)節(jié)點(diǎn)運(yùn)動(dòng)每次距離小于0.5 m，節(jié)點(diǎn)就不進(jìn)行移動(dòng)，以節(jié)約能量。

2．4 算法的計(jì)算復(fù)雜性分析

由上述算法可知，算法的基本運(yùn)算為算法的步驟b)c）。步驟b)的時(shí)間復(fù)雜性為O(n(n-1))；步驟c)的時(shí)間復(fù)雜性為O(n2)。在有限次循環(huán)內(nèi)完成節(jié)點(diǎn)部署后，總的時(shí)間復(fù)雜性為O(t(n(n-1)+n2))=O(n2)。

3 仿真實(shí)驗(yàn)及分析

3．1 仿真實(shí)驗(yàn)的建立

本文使用圖形化編程語(yǔ)言LabVIEW開(kāi)發(fā)平臺(tái)編制了移動(dòng)感知網(wǎng)節(jié)點(diǎn)部署的仿真程序。參數(shù)設(shè)置為L=100 m，cr=20 m，sr=10 m，tmax＝20，kR=kB=0.2，m=1，kd=1。選擇了不同節(jié)點(diǎn)數(shù)進(jìn)行仿真：a）n=20;b)n=35;c)n=50。n代表移動(dòng)節(jié)點(diǎn)數(shù)。

圖1所示是第n=35的節(jié)點(diǎn)運(yùn)動(dòng)軌跡仿真結(jié)果。在圖1中，網(wǎng)格狀區(qū)域表示待感知區(qū)域，小空心圓代表移動(dòng)節(jié)點(diǎn)的初始位置，小實(shí)心圓表示經(jīng)過(guò)20次迭代運(yùn)算后，移動(dòng)節(jié)點(diǎn)最終到達(dá)的位置。從圖1中可以看到，移動(dòng)節(jié)點(diǎn)從傳感器密集區(qū)域運(yùn)動(dòng)到空曠的區(qū)域，從而使節(jié)點(diǎn)分布更均勻、節(jié)點(diǎn)的覆蓋范圍更大，并且可以看到機(jī)器人沒(méi)有發(fā)生任何碰撞。

3．2 感知網(wǎng)的性能分析

圖2是三種不同數(shù)目節(jié)點(diǎn)隨迭代次數(shù)變化的節(jié)點(diǎn)覆蓋率變化。在這三種情況下，移動(dòng)節(jié)點(diǎn)不同，都是隨機(jī)分布在中心區(qū)域。從圖2的數(shù)據(jù)可以看出，在三種情況下覆蓋率都有提高，在n=50，由50個(gè)移動(dòng)節(jié)點(diǎn)組成感知網(wǎng)，覆蓋率由12．6%提高到96.4%，并且在第14次迭代后感知網(wǎng)已達(dá)到穩(wěn)定狀態(tài)，覆蓋率不再變化。其他兩種形式的感知網(wǎng)的覆蓋率也都有所提高，并且在20次迭代后基本達(dá)到了穩(wěn)定狀態(tài)。從覆蓋率的變化可以發(fā)現(xiàn)，完全由移動(dòng)節(jié)點(diǎn)組成的感知網(wǎng)覆蓋率提高得最大。

圖3所示是感知網(wǎng)節(jié)點(diǎn)均勻性隨迭代次數(shù)變化的曲線圖。根據(jù)感知網(wǎng)節(jié)點(diǎn)均勻性的定義， 三種不同數(shù)目節(jié)點(diǎn)形式都不同程度地提高了感知網(wǎng)的節(jié)點(diǎn)均勻性，每個(gè)節(jié)點(diǎn)都進(jìn)行拓?fù)渥兓瑥亩_(dá)到最好的節(jié)點(diǎn)均勻分布狀態(tài)。圖4 所示是不同數(shù)目節(jié)點(diǎn)形式情況下每次迭代后，感知網(wǎng)移動(dòng)節(jié)點(diǎn)運(yùn)行的總距離，也可以近似代表移動(dòng)節(jié)點(diǎn)的能量消耗。從圖4中可以看出，網(wǎng)絡(luò)覆蓋率的提高是以犧牲能量為代價(jià)的。

由移動(dòng)節(jié)點(diǎn)組成的感知網(wǎng)可以達(dá)到最高的覆蓋率和分布均勻性，但在實(shí)際應(yīng)用中，完全由移動(dòng)節(jié)點(diǎn)組成感知網(wǎng)在成本上會(huì)遠(yuǎn)遠(yuǎn)高于完全由靜態(tài)節(jié)點(diǎn)組成的感知網(wǎng)，但靜態(tài)感知網(wǎng)最大的弱點(diǎn)是它不能進(jìn)行再部署。在實(shí)際應(yīng)用中，會(huì)由于節(jié)點(diǎn)失效或部署時(shí)的非均勻性造成網(wǎng)絡(luò)的傳輸分割，以至于不能工作，所以使用移動(dòng)感知網(wǎng)可以極大提高網(wǎng)絡(luò)節(jié)點(diǎn)的再部署，從而使感知網(wǎng)的生命得以延長(zhǎng)。

3．3 MSCA與模擬退火算法的性能比較

為了驗(yàn)證所提出的MSCA性能的高效性，本文將MSCA與模擬退火算法(simulated annealing algorithm，SA)進(jìn)行了性能比較。

SA中的主要參數(shù)與MSCA中的參數(shù)基本一致。在SA中，如果本次循環(huán)的移動(dòng)節(jié)點(diǎn)運(yùn)行總距離Dn小于上次循環(huán)的總距離Do，則接受本次節(jié)點(diǎn)運(yùn)行過(guò)程，并作為新的運(yùn)行方案；否則，以概率p=exp(-(Dn-Do)/T)接受本次運(yùn)行方案。其中T是當(dāng)前溫度。圖5是不同移動(dòng)節(jié)點(diǎn)數(shù)時(shí)，最終達(dá)到覆蓋率的比較。雖然移動(dòng)節(jié)點(diǎn)數(shù)不同，但從圖5中可以看出，MSCA在覆蓋率上略好于SA。

圖6是移動(dòng)節(jié)點(diǎn)運(yùn)行總距離的比較。從圖6可以看出，MSCA明顯好于SA，使用MSCA的節(jié)點(diǎn)部署運(yùn)行的總距離要遠(yuǎn)遠(yuǎn)小于使用SA運(yùn)行的總距離，相差一個(gè)數(shù)量級(jí)。這是因?yàn)镸SCA是一種啟發(fā)式的算法，也是一種分布式算法；而SA中，每個(gè)移動(dòng)節(jié)點(diǎn)作為一個(gè)粒子首先進(jìn)行的是一種無(wú)序運(yùn)動(dòng)，而在退火階段才逐步達(dá)到有序運(yùn)動(dòng)，所以運(yùn)行的距離要長(zhǎng)，同時(shí)消耗了大量的能量。雖然使用SA也可以達(dá)到部署優(yōu)化，但在實(shí)際應(yīng)用中，這種方式是難以進(jìn)行的。從實(shí)際應(yīng)用的角度， MSCA是可取的。

4 結(jié)束語(yǔ)

本文基于機(jī)器人的局部信息和人工勢(shì)場(chǎng)法提出了一種移動(dòng)感知節(jié)點(diǎn)的覆蓋方法，在理論上分析了它的可行性。在感知網(wǎng)中，移動(dòng)節(jié)點(diǎn)具有移動(dòng)的特性，對(duì)感知網(wǎng)節(jié)點(diǎn)的部署和重構(gòu)具有很大的靈活性，在感知網(wǎng)絡(luò)的區(qū)域覆蓋上，比單純由靜態(tài)傳感器組成的感知網(wǎng)具有魯棒性。雖然人工勢(shì)場(chǎng)法存在局部極小的缺陷，但是通過(guò)仿真實(shí)驗(yàn)可以看出，采用這種算法可以快速對(duì)感知區(qū)域進(jìn)行節(jié)點(diǎn)覆蓋，也是一種分布式控制方法，對(duì)移動(dòng)感知網(wǎng)的覆蓋率、均勻性都有很大的提高。這種覆蓋方法不需要預(yù)先知道環(huán)境地圖，無(wú)須進(jìn)行集中控制，能夠?qū)崿F(xiàn)動(dòng)態(tài)網(wǎng)絡(luò)節(jié)點(diǎn)的調(diào)整，對(duì)于戰(zhàn)場(chǎng)或污染地區(qū)的偵察監(jiān)控等實(shí)際應(yīng)用領(lǐng)域有一定的現(xiàn)實(shí)意義。 

參考文獻(xiàn)：

［1］AKYILDIZ I F，SU W，SANKARASUBRAMANIAM Y，et al.Wireless sensor networks:a survey[J].Computer Networks，2002，38(4): 393-422.

[2]MEGUERDICHIAN S，KOUSHANFAR F，POTKONJAK M，et al.Coverage problems in wireless Ad hoc sensor network[C]//Proc of the 20th Annual Joint Conference of the IEEE Computer and Communications Societies.Anchorage:IEEE Press，2001:13801387.

[3]WATTENHOFER R，LI L，BAHL P，et al.Distributed topology control for wireless multihop Ad hoc networks[C]//Proc of the 20th Annual Joint Conference of the IEEE Computer and Commpunications Societies.Anchorage:IEEE Press，2001:13881397.

[4]LI Xiangyang，WAN Penjun，F(xiàn)RIEDER O.Coverage in wireless Ad hoc sensor networks[J].IEEE Trans on Computer，2003，52(6): 753763.

[5]HOWARD A，MATARIC M J，SUKHATME G S.An incremental selfdeployment algorithm for mobile sensor networks[J].Autonomous Robots，2002，13(2): 113126.

[6]ZOU Yi，CHAKRABARTY K.Sensor deployment and target localization based on virtual forces[C]//Proc of the 22nd Annual Joint Conference of the IEEE Computer and Commpunications Societies.San Francisco：IEEE Press，2003:12931303.

[7]WANG Guilin，CAO Guohong，La PORTAL T.Movementassisted sensor deployment[J].

IEEE Trans on Mobile Computing，2006，5(6):640-652.

[8]HOWARD A，MATARIC M J，SUKHATME G S.Mobile sensor network deployment using potential fields:a distributed，scalable solution to the area coverage problem[C]//Proc of the 6th International Symposium on Distributed Autonomous Robotics Systems.London:SpringerVerlag，2002:299-308.

[9]CORTES J，MARTINEZ S，KARATAS T，et al.Coverage control for mobile sensing networks[J].IEEE Trans on Robotics and Automation，2004，20(2): 243-255.

[10]HEO N，VARSHNEY P K.An intelligent deployment and clustering algorithm for a distributed mobile sensor network[C]//Proc of IEEE International Conference on Systems，Man and Cybernetics.Piscataway:IEEE Press，2003:4576-4581.

注：“本文中所涉及到的圖表、注解、公式等內(nèi)容請(qǐng)以PDF格式閱讀原文。”