張 華，劉玉良

(浙江海洋學(xué)院機(jī)電工程學(xué)院，浙江舟山 316004)

無線傳感器網(wǎng)絡(luò)應(yīng)用中，重要的是監(jiān)測(cè)目標(biāo)的具體位置，沒有確切監(jiān)測(cè)消息的位置沒有任何意義[1]，而網(wǎng)絡(luò)的覆蓋情況則是保證網(wǎng)絡(luò)使我們了解是否存在監(jiān)測(cè)和通信盲區(qū)，了解被監(jiān)測(cè)區(qū)域的無線傳感器網(wǎng)絡(luò)的覆蓋情況，從而重新調(diào)整傳感器節(jié)點(diǎn)分布或者指導(dǎo)在將來添加傳感器節(jié)點(diǎn)時(shí)可采取的改進(jìn)措施。以通過調(diào)整網(wǎng)絡(luò)覆蓋的密度，對(duì)被監(jiān)測(cè)區(qū)域中重要區(qū)域設(shè)置熱點(diǎn)，部署更多的傳感器節(jié)點(diǎn)，保證測(cè)量數(shù)據(jù)的可靠性[2-4]。按照定位過程中是否需要測(cè)量節(jié)點(diǎn)之間的實(shí)際距離，把定位算法分為，基于距離的定位算法和距離無關(guān)的定位算法。

水聲通信網(wǎng)絡(luò)的研究起步于20世紀(jì)90年代。美國計(jì)算機(jī)學(xué)會(huì)從2006年開始成立了國際工作組，專門開展水下聲傳感器網(wǎng)絡(luò)的研究和交流。美國多所大學(xué)，包括麻省理工、喬治亞理工等都成立水下聲傳感器網(wǎng)絡(luò)課題組開展專門的研究工作[5-9]。國內(nèi)，水聲傳感器網(wǎng)絡(luò)方面的研究也才剛剛開始，2006年，中科院聲學(xué)所、哈爾濱工程大學(xué)、北京科技大學(xué)等研究單位在863計(jì)劃的支持下，結(jié)合多年水聲通信的研究經(jīng)驗(yàn)，開展水下聲傳感器網(wǎng)絡(luò)的相關(guān)研究[10-12]。

從現(xiàn)有的文獻(xiàn)來看，對(duì)水聲無線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)覆蓋及自定位的問題開展比較少。筆者主要研究水下傳感器網(wǎng)絡(luò)二維情況下節(jié)點(diǎn)覆蓋及其自定位問題，采用概率感知模型研究如何提高節(jié)點(diǎn)覆蓋概率，在此基礎(chǔ)上，探討節(jié)點(diǎn)自定位問題，再采用遺傳算法對(duì)節(jié)點(diǎn)的覆蓋與自定位進(jìn)行優(yōu)化，從而實(shí)現(xiàn)節(jié)點(diǎn)覆蓋及其自定位的優(yōu)化控制。

1 問題描述及數(shù)學(xué)模型

從現(xiàn)有的文獻(xiàn)和研究[13-18]來看，無線傳感器網(wǎng)絡(luò)以隨機(jī)拋灑形式分布的節(jié)點(diǎn)一般有：均勻分布、高斯分布、瑞利分布等，其中以高斯分布最常見。在實(shí)際應(yīng)用環(huán)境中，由于環(huán)境噪聲干擾以及信號(hào)強(qiáng)度隨傳輸距離衰減，傳感器節(jié)點(diǎn)的檢測(cè)能力表現(xiàn)出一定的不確定性，概率感知模型反映了這種不確定性。在概率感知模型中，某傳感器節(jié)點(diǎn)x檢測(cè)到任意點(diǎn)P處發(fā)生的事件的概率為：

假設(shè)監(jiān)測(cè)區(qū)域xlength×ylength，其中xlength，ylength分別是該坐標(biāo)對(duì)象的橫坐標(biāo)長度和縱坐標(biāo)長度，隨機(jī)布撒一定數(shù)量的節(jié)點(diǎn)作為信標(biāo)節(jié)點(diǎn)，各個(gè)節(jié)點(diǎn)坐標(biāo)通過相互通信或者位置等信息，各節(jié)點(diǎn)坐標(biāo)分別為P(ixi，y)i，(i=1，2，…，n)，隨機(jī)布撒若干未知節(jié)點(diǎn)，未知節(jié)點(diǎn)坐標(biāo)為X(jxj，y)j，(j=1，2，…，m)，該節(jié)點(diǎn)與各信標(biāo)節(jié)點(diǎn)的距離分別為di，( i=1，2，…，n)；同時(shí)，此監(jiān)測(cè)區(qū)域被數(shù)字離散化為若干個(gè)像素(像素主要指信標(biāo)節(jié)點(diǎn))，像素點(diǎn)坐標(biāo)為(x，y)，則目標(biāo)像素點(diǎn)與未知傳感器節(jié)點(diǎn)的距離素點(diǎn)被傳感器節(jié)點(diǎn)所覆蓋的事件定義為ni，則該事件發(fā)生的概率P(n)i即為像素點(diǎn)(x，y)被傳感器節(jié)點(diǎn)Ni所覆蓋的概率[19-20]：

實(shí)際上由于監(jiān)測(cè)環(huán)境和噪聲干擾，傳感節(jié)點(diǎn)測(cè)量模型應(yīng)呈一定特性的概率分布，即：

其中，re(0＜re＜r)，α1，α2，β1，β2，是與傳感節(jié)點(diǎn)特性有關(guān)的測(cè)量參數(shù)，λ1，λ2為輸入?yún)?shù):

為提高目標(biāo)測(cè)量概率，需采用多個(gè)傳感節(jié)點(diǎn)同時(shí)測(cè)量目標(biāo)。聯(lián)合測(cè)量概率如下:

其中，Nov為測(cè)量目標(biāo)的傳感節(jié)點(diǎn)集合。由于實(shí)際中存在測(cè)量誤差，節(jié)點(diǎn)間的測(cè)量距離跟坐標(biāo)距離之間存在誤差值，該節(jié)點(diǎn)與各信標(biāo)節(jié)點(diǎn)的測(cè)距誤差分別為δi，(i=1，2，…，n)；根據(jù)上述問題描述，按歐式距離建立該未知節(jié)點(diǎn)X(xest，yest)和與其通信的各信標(biāo)節(jié)點(diǎn)之間建立方程組如下，

公式(5)以未知節(jié)點(diǎn)和信標(biāo)節(jié)點(diǎn)間的距離作為約束力，制約了未知節(jié)點(diǎn)坐標(biāo)的范圍，若傳感器節(jié)點(diǎn)處于理想狀況之下，左側(cè)結(jié)果都應(yīng)為0，故各誤差值之和越小越趨向于理想狀態(tài)，即：

未知節(jié)點(diǎn)要測(cè)算自身的最佳位置問題可以轉(zhuǎn)換成尋找公式6中絕對(duì)值的和最小值。

2 遺傳算法原理及設(shè)計(jì)

2.1 遺傳算法及算子

遺傳算法是模仿了生物的遺傳進(jìn)化機(jī)制進(jìn)行自然選擇和遺傳的一種尋優(yōu)算法，具有簡單、精度高等特點(diǎn)，廣泛應(yīng)用于人工智能、神經(jīng)網(wǎng)絡(luò)等領(lǐng)域。在遺傳算法中，算子的選擇至關(guān)重要，包括選擇選擇算子，交叉算子，變異算子，其中交叉算子決定了該算法的全局搜索最優(yōu)解能力，變異算子則決定了算法的局部搜索最優(yōu)解的能力[15]。各遺傳算子的選擇如下：

選擇操作建立在對(duì)個(gè)體的適應(yīng)度進(jìn)行評(píng)價(jià)的基礎(chǔ)之上，適應(yīng)度較高的個(gè)體被遺傳到下一代的概率較大，適應(yīng)度較低的個(gè)體被遺傳到下一代的機(jī)會(huì)較少，從種群中使用隨機(jī)遍歷抽樣方式選擇適應(yīng)度較高的個(gè)體，選擇的概率取GGAP。已知的交叉操作主要包含了交叉點(diǎn)的位置和如何交換部分基因的方式。本文采用算術(shù)交叉，算術(shù)交叉(Arithmetic Crossover)是指由兩個(gè)個(gè)體的線性組合而產(chǎn)生出兩個(gè)新的個(gè)體。設(shè)有父代兩個(gè)個(gè)體g1，g2，進(jìn)行交叉后將得到兩個(gè)子代g1，g2，表達(dá)式分別是：

α也可以是一個(gè)由進(jìn)化代數(shù)所決定的變量(此時(shí)，所進(jìn)行的交叉運(yùn)算稱為非均勻運(yùn)算)。算術(shù)交叉的主要操作過程為：首先確定兩個(gè)個(gè)體進(jìn)行線性組合時(shí)的系數(shù)α；根據(jù)上述公式生成兩個(gè)新的個(gè)體；交叉概率為Pc。變異算子是產(chǎn)生新個(gè)體的輔助方法，決定了遺傳算法的局部搜索能力。設(shè)s=(v1，v2，…vn)是一個(gè)父代解，其中分量 vi被選擇為進(jìn)行變異，其定義區(qū)間為[ai，bi]，則變異后的父代解為 s′=(v1，v2，…vi-1，vi+1，…vn)，其中可表示為：

這里，“0”，“1”代表變異的方向，γ 是在區(qū)間[0，1]的隨機(jī)數(shù)，k 是系數(shù)，范圍在 0～1 之間，random 是隨機(jī)產(chǎn)生0和1。其中，(T，y)=y(1-γT2)，T代表最大代數(shù)。變異概率取Pm。

2.2 遺傳算法實(shí)現(xiàn)及步驟

2.2.1 位置獲取及覆蓋控制

在第1階段，首先是所有節(jié)點(diǎn)初始化，信標(biāo)節(jié)點(diǎn)獲知自身各類信息，并自動(dòng)向外廣播自身位置信息，未知節(jié)點(diǎn)接收后，保存并將該信息轉(zhuǎn)播一次；在第2階段，信標(biāo)節(jié)點(diǎn)(像素點(diǎn))根據(jù)所獲知的信息對(duì)覆蓋區(qū)域內(nèi)的所有未知節(jié)點(diǎn)進(jìn)行覆蓋測(cè)算，以獲取未知節(jié)點(diǎn)能夠被覆蓋并定位的可能性，進(jìn)而將所獲得信息轉(zhuǎn)發(fā)至周圍能夠通信的未知節(jié)點(diǎn)；在第3階段，未知節(jié)點(diǎn)根據(jù)轉(zhuǎn)發(fā)的信息，根據(jù)覆蓋概率的大小，決定是否進(jìn)行定位(本文設(shè)置覆蓋概率大于等于80%的未知節(jié)點(diǎn)能夠進(jìn)行有效定位)；在第4階段，能夠進(jìn)行有效定位的節(jié)點(diǎn)，根據(jù)節(jié)點(diǎn)的定位算法，進(jìn)行定位；第5階段，自行進(jìn)行迭代計(jì)算的定位算法的進(jìn)化過程比較慢，并且精度不太高，因而用遺傳算法對(duì)未知節(jié)點(diǎn)進(jìn)行優(yōu)化計(jì)算，優(yōu)化計(jì)算過程包括初始化種群，選擇操作，變異操作和交叉操作，還包括計(jì)算停止條件。

2.2.2 算法步驟

步驟1，所有節(jié)點(diǎn)初始化，信標(biāo)節(jié)點(diǎn)向外廣播自身信息，未知節(jié)點(diǎn)獲取信息后保存并轉(zhuǎn)發(fā)一次；

步驟2，信標(biāo)節(jié)點(diǎn)根據(jù)所獲知信息，采用公式2對(duì)單個(gè)節(jié)點(diǎn)進(jìn)行覆蓋計(jì)算(在實(shí)際算法中，可采用公式4對(duì)多個(gè)節(jié)點(diǎn)進(jìn)行聯(lián)合覆蓋計(jì)算)；

步驟3，未知節(jié)點(diǎn)根據(jù)指令，自動(dòng)剔除覆蓋率過低的未知節(jié)點(diǎn)，覆蓋率較高的未知節(jié)點(diǎn)進(jìn)入定位程序計(jì)算；

步驟4，采用遺傳算法，根據(jù)未知節(jié)點(diǎn)給定信息對(duì)種群進(jìn)行初始化設(shè)計(jì)，給出符合運(yùn)算的二進(jìn)制種群；

步驟5，根據(jù)二進(jìn)制種群，依據(jù)定位公式5，進(jìn)行選擇操作，并設(shè)定選擇概率；

步驟6，依據(jù)公式7實(shí)現(xiàn)交叉操作，并設(shè)置變異率的參數(shù)；

步驟7，依據(jù)公式8實(shí)現(xiàn)變異操作，并設(shè)置交叉率的參數(shù)；

步驟8，根據(jù)定位指標(biāo)設(shè)置遺傳算法精度，根據(jù)算法精度要求觀察步驟7的結(jié)果是否符合要求，不能達(dá)到精度要求，轉(zhuǎn)到步驟5，重新進(jìn)行迭代運(yùn)算；如果達(dá)到精度要求，則轉(zhuǎn)入步驟9；

步驟9，輸出結(jié)果，整體覆蓋概率以及定位參數(shù)等，程序運(yùn)行結(jié)束。

3 仿真結(jié)果與分析

在100×100范圍內(nèi)布置30個(gè)信標(biāo)節(jié)點(diǎn)，10個(gè)未知節(jié)點(diǎn)，取個(gè)體數(shù)目為40個(gè)，遺傳迭代次數(shù)為25次，代溝取0.9，變異概率取0.3，交叉概率取0.7。采用主頻為3G的計(jì)算機(jī)，在matlab7.0.1環(huán)境下進(jìn)行仿真。

圖1 節(jié)點(diǎn)初始化覆蓋狀況Fig.1 Cover condition of node initialization

圖2 迭代次數(shù)與覆蓋率Fig.2 The number of iterations and coverage

圖3 覆蓋率與感知半徑Fig.3 Coverage and perception radius

圖4 迭代次數(shù)與種群數(shù)量Fig.4 The number of iterations and population

圖5 信標(biāo)節(jié)點(diǎn)密度與定位誤差Fig.5 Position error and density of anchor nodes

圖6 均值和最優(yōu)解分布Fig.6 Distribution of mean and the optimal solution

圖1表示水下傳感器節(jié)點(diǎn)初始化分布圖?，F(xiàn)有文獻(xiàn)研究[19]表明傳感器節(jié)點(diǎn)的初始分布對(duì)節(jié)點(diǎn)的覆蓋概率影響不大。圖2表示算法的迭代次數(shù)與未知節(jié)點(diǎn)的覆蓋概率的關(guān)系，表明迭代次數(shù)較少時(shí)，覆蓋概率不高；當(dāng)?shù)螖?shù)達(dá)到一定程度時(shí)，覆蓋概率不受迭代次數(shù)影響。圖3表示的是覆蓋概率與感知半徑之間的關(guān)系，感知半徑越大，未知節(jié)點(diǎn)接受到信標(biāo)節(jié)點(diǎn)的信息越多，因而受到覆蓋的可能性也越大；當(dāng)感知半徑達(dá)到一定數(shù)值以后，對(duì)覆蓋概率影響不大。圖4表示迭代次數(shù)與初始的種群數(shù)量之間的關(guān)系，從圖中可以看出，種群數(shù)量對(duì)迭代次數(shù)影響不大。圖5表示信標(biāo)節(jié)點(diǎn)密度與節(jié)點(diǎn)自定的誤差之間的關(guān)系，表明當(dāng)信標(biāo)節(jié)點(diǎn)密度較低時(shí)，定位誤差很大，當(dāng)信標(biāo)節(jié)點(diǎn)密度在不斷增加時(shí)，定位誤差的精度在不斷降低，圖中數(shù)據(jù)表明，當(dāng)信標(biāo)節(jié)點(diǎn)的密度達(dá)到35%以后，定位精度受此影響幾乎不會(huì)改變。圖6表示定位過程中，節(jié)點(diǎn)自定位的誤差的均值以及最佳解，從圖中可以看出，當(dāng)?shù)螖?shù)在不斷增加時(shí)，節(jié)點(diǎn)定位誤差在不斷減少，從而提高整體定位精度。

4 小結(jié)

水下傳感器網(wǎng)絡(luò)是海洋戰(zhàn)略中重要的一環(huán)，節(jié)點(diǎn)覆蓋及其自定位則是水下傳感器網(wǎng)絡(luò)的關(guān)鍵技術(shù)之一。本文采用概率感知模型對(duì)節(jié)點(diǎn)進(jìn)行覆蓋計(jì)算，再對(duì)覆蓋概率較高的節(jié)點(diǎn)進(jìn)行自定位，最后采用遺傳算法進(jìn)行定位精度尋優(yōu)迭代。仿真表明，迭代次數(shù)對(duì)未知節(jié)點(diǎn)的覆蓋概率有較大影響；感知半徑越大，覆蓋概率越高，當(dāng)半徑達(dá)到一定程度后，對(duì)覆蓋概率影響有限；信標(biāo)節(jié)點(diǎn)的密度的高低影響節(jié)點(diǎn)自定的精度?？偠灾?，遺傳算法能夠有效的對(duì)水下傳感器節(jié)點(diǎn)覆蓋及其自定位進(jìn)行優(yōu)化。

[1]孫利民,李建中,陳 渝,等.無線傳感器網(wǎng)絡(luò)[M].北京:清華大學(xué)出版社,2005.

[2]BULUSU N,HEIDEMANN J,ESTRIN D,et al.Density adaptive algorithms for beacon placement in wireless sensor networks[C]//IEEE ICDCS’01(Phoenix,AZ).2001.

[3]HE Tian,HUANG Cheng-du,BLUM B M,et al.Range-Free Localization Schemes in Large Scale Sensor Networks[C]//Proceedings of the 9th Annual Inter2 National Conference on Mobile Computing and Networking(MobiCom).San Diego,California,USA:ACM Press,2003:81-95.

[4]PATWARI N,ASH JN,KYPEROUNTAS S,et al.Locating the nodes:cooperative localization in wireless sensor networks[J].Signal Processing Magazine,IEEE,2005,22(4):54-69.

[5]田金鵬.無線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)定位技術(shù)研究[D].上海:上海大學(xué),2009.

[6]周 全,朱紅松,徐勇軍,等.基于最小包含圓的無線傳感器網(wǎng)絡(luò)定位算法[J].通信學(xué)報(bào)2008,29(11):84-90.

[7]蔣 杰,方 力,張鶴穎,等.無線傳感器網(wǎng)絡(luò)最小連通覆蓋集問題求解算法[J].軟件學(xué)報(bào),2006,17(2):175-184.

[8]李兆斌,魏占禎,徐鳳麟.無線傳感器網(wǎng)絡(luò)增強(qiáng)的質(zhì)心定位算法及性能分析[J].傳感技術(shù)學(xué)報(bào),2009(4):563-566.

[9]MAO Guo-qiang,FIDAN B,ANDERSON B.Wireless sensor network localization techniques[J].Computer Networks,2007,51(10):2 529-2 553.

[10]LANGENDOEN K,REIJERS N.Distributed localization in wireless sensor networks:a quantitative comparison[J].Computer Networks,2003,43(4):499-518.

[11]曹正文,趙 健,高寶建.基于加權(quán)最小二乘法的紅外多站定位的研究[J].光子學(xué)報(bào),2005,34(7):1001-1004.

[12]CARDEI M,Du Ding-zhu.Improving wireless sensor network lifetime through power aware organization[J].ACM Wireless Networks,2005,11(3):333-340.

[13]程銘東.基于遺傳算法的多傳感器網(wǎng)絡(luò)中目標(biāo)定位算法[J].計(jì)算機(jī)工程與應(yīng)用,2008,44(16):105-107.

[14]YI.Zou,KRISHNENDU CHAKRABARTY.Sensor Deployment and Target Localization in Distributed Sensor Networks[J].ACM Transactions on Embedded Computing Systems,2004,3(1):61-91.

[15]NICULESCU D.Positioning in ad hoc sensor networks.Network[J].IEEE,2004,18(4):24-29.

[16]曹 峰,劉麗萍,王 智.能量有效的無線傳感器網(wǎng)絡(luò)部署[J].信息與控制,2006,35(2):147-153.

[17]RICE J.Telesonar signaling and Seaweb underwater wireless networks[J].New Information Processing Techniques for Military Systems,2001,(17):1-13.

[18]ANGELINE P J.Using Selection to improve Particle Swarm Optimization[R]//Proceedings of the IEEE Congress on Evolutionary Computation,ICEC,1998:84-89.

[19]張文愛,劉麗芳,李孝榮.基于粒子進(jìn)化的多粒子群優(yōu)化算法[J].計(jì)算機(jī)工程與應(yīng)用,2008,44(7):51-53.

[20]WANG Xue,WANG Sheng,MA Jun-jie.Dynamic deployment optimization in wireless sensor network[J].Lecture Notes in Control and Information Science,2006,344:182-187.