張 華，劉玉良

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2.1 遺傳算法及算子

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

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

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

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

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

2.2.1 位置獲取及覆蓋控制

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

2.2.2 算法步驟

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

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

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

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

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

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

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

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

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

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

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

圖1 節(jié)點初始化覆蓋狀況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é)點密度與定位誤差Fig.5 Position error and density of anchor nodes

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

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

4 小結(jié)

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

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

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

[8]李兆斌,魏占禎,徐鳳麟.無線傳感器網(wǎng)絡(luò)增強的質(zhì)心定位算法及性能分析[J].傳感技術(shù)學(xué)報,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é)報,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].計算機工程與應(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].計算機工程與應(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.