水聲傳感器網(wǎng)絡(luò)節(jié)點自定位的遺傳算法優(yōu)化研究

謝遠(yuǎn)黨，徐榮偉，張 華

（1.浙江海洋學(xué)院機電工程學(xué)院，浙江舟山 316004;2.舟山萬達(dá)船舶設(shè)計有限公司，浙江舟山 316101）

無線傳感器網(wǎng)絡(luò)應(yīng)用中，重要的是監(jiān)測目標(biāo)的具體位置，沒有確切監(jiān)測消息的位置沒有任何意義。按照定位過程中是否需要測量節(jié)點之間的實際距離，把定位算法分為，基于距離的定位算法和距離無關(guān)的定位算法。距離無關(guān)的定位機制定位性能受環(huán)境因素的影響小，雖然定位的誤差相應(yīng)有所增加，但定位精度能夠滿足多數(shù)傳感器網(wǎng)絡(luò)的應(yīng)用要求，是目前大家普遍重點關(guān)注的定位機制[1-2]。

質(zhì)心算法是一種僅基于網(wǎng)絡(luò)節(jié)點連通性的定位算法，定位精度取決于信標(biāo)節(jié)點的密度和分布。許多人針對質(zhì)心算法提出了改進(jìn)，文獻(xiàn)[3]中提出一種采用最小二乘原理構(gòu)建的加權(quán)定位算法思路，該算法需要測距誤差的均方值；文獻(xiàn)[1]提出一種密度自適應(yīng)的HEAP算法，通過在信標(biāo)節(jié)點密度低的區(qū)域增加新標(biāo)節(jié)點，以提高定位的精度；文獻(xiàn)[4]中提對距離無關(guān)的幾種定位機制進(jìn)行了比較，信標(biāo)節(jié)點密度的大小影響了定位精度的高低。陸地傳感網(wǎng)一樣，水下無線傳感網(wǎng)中，節(jié)點的位置信息同樣是數(shù)據(jù)采集必不可少的一部分。水聲傳感器網(wǎng)絡(luò)是陸地?zé)o線傳感器網(wǎng)絡(luò)概念向水下應(yīng)用的延伸,由多個傳感器節(jié)點組成。

1 水聲通信網(wǎng)絡(luò)概述

水聲通信是利用聲波在海水里傳播實現(xiàn)的?；竟ぷ髟硎窍葘⑽淖帧⒄Z音、圖像等信息轉(zhuǎn)換成電信號，進(jìn)行數(shù)字化處理，換能器又將電信號轉(zhuǎn)換為聲信號進(jìn)行發(fā)送；聲信號通過水介質(zhì)，將信息傳遞到接收換能器，聲信號轉(zhuǎn)換成電信號，解碼器將數(shù)字信息解碼，再將信息變成聲音、文字及圖片。

水聲通信網(wǎng)絡(luò)的研究起步于20世紀(jì)90年代。美國計算機學(xué)會從2006年開始成立了國際工作組，專門開展水下聲傳感器網(wǎng)絡(luò)的研究和交流。美國的多所著名大學(xué)，都開展了水下聲傳感器網(wǎng)絡(luò)課題的專門研究工作[5-6]。國內(nèi)，水聲傳感器網(wǎng)絡(luò)方面的研究也才剛剛開始，2006年，哈爾濱工程大學(xué)、北京科技大學(xué)等研究單位在863計劃的支持下，結(jié)合多年水聲通信的研究經(jīng)驗，開展水下聲傳感器網(wǎng)絡(luò)的相關(guān)研究[7-9]。目前的水聲傳感器網(wǎng)絡(luò)主要有兩種拓?fù)浣Y(jié)構(gòu)，即二維水下傳感器網(wǎng)絡(luò)和三維水下傳感器網(wǎng)絡(luò)[10]。在二維水聲傳感器網(wǎng)絡(luò)的系統(tǒng)模型中，傳感器節(jié)點被放置在海洋底部,主要應(yīng)用于海洋環(huán)境的監(jiān)測和海底板塊構(gòu)造的研究領(lǐng)域。文獻(xiàn)[11]討論了在傳感器網(wǎng)絡(luò)節(jié)點自定位問題，并分RANGE，AOA，AOA+RANGE，AOA+COMPASS，AOA+COMPASS+RANGE幾種情況進(jìn)行探討，證實了傳感器網(wǎng)絡(luò)能夠定位并傳輸數(shù)據(jù)。

從現(xiàn)有的文獻(xiàn)來看，對水聲無線傳感器網(wǎng)絡(luò)節(jié)點自定位的問題開展比較少，陸地上無線傳感器網(wǎng)絡(luò)自定位相對較多。水下傳感器網(wǎng)絡(luò)二維模型如圖1，本文主要研究水下傳感器網(wǎng)絡(luò)二維情況下節(jié)點的自定位問題，采用遺傳算法優(yōu)化節(jié)點自定位的精度，實現(xiàn)節(jié)點自定位的優(yōu)化控制。

圖1 水下傳感器網(wǎng)絡(luò)二維分布模型Fig.1 Sensor water under distribution network model of a two-dimensional sensor

2 定位數(shù)學(xué)模型

從現(xiàn)有的文獻(xiàn)和研究來看，陸地上無線傳感器網(wǎng)絡(luò)以隨機拋灑形式分布，包括均勻分布、高斯分布、瑞利分布等，其中以高斯分布最常見。在探討無線傳感器網(wǎng)絡(luò)節(jié)點自定位以及節(jié)點覆蓋的絕大部分的文獻(xiàn)中，對節(jié)點的信號傳播模型采取了圓形無線信號傳播模型，節(jié)點分布選取均勻分布，在實際使用中，無線信號的傳播模型是按信號傳輸強度的等高線分布，與理想的圓形模型有很大區(qū)別，因而也會造成節(jié)點自定位的誤差，然而水聲無線傳感器網(wǎng)絡(luò)的節(jié)點分布的復(fù)雜程度遠(yuǎn)遠(yuǎn)超過了陸地，比如信標(biāo)節(jié)點自身的位置信息，陸地上的節(jié)點可以攜帶GPS等測量儀器，在水下卻不能采取同樣方式實現(xiàn)。文獻(xiàn)[12]概述了目前水聲傳感器網(wǎng)絡(luò)的應(yīng)用前景和所面臨的挑戰(zhàn)，并對短距離聲通信和MAC協(xié)議等進(jìn)行了討論，本文選取節(jié)點為均勻分布模型，通信模型取橢圓形模型，以替代等高線模型，減少通信模型對節(jié)點自定位的誤差。

假定研究對象為二維平面，區(qū)域大小為xlength×ylength，其中xlength，ylength分別是該坐標(biāo)對象的橫坐標(biāo)長度和縱坐標(biāo)長度；隨機布撒數(shù)量為N的節(jié)點作為信標(biāo)節(jié)點，各個節(jié)點通過相互通信獲得坐標(biāo)或者網(wǎng)絡(luò)中的位置等信息，各節(jié)點坐標(biāo)分別為Pi（xi，yi），（i=1，2，…，n），信標(biāo)節(jié)點均勻分布；隨機布撒未知節(jié)點，數(shù)量為m個，未知節(jié)點坐標(biāo)為Xj（xj，yj），（j=1，2，…，n）；對每個未知節(jié)點而言真實坐標(biāo)跟估算坐標(biāo)以及質(zhì)心坐標(biāo)都不相同，設(shè)某未知節(jié)點坐標(biāo)X（xest，yest），與其通信的信標(biāo)節(jié)點按質(zhì)心算法建成一個質(zhì)心坐標(biāo)X（xav，yav），它們之間存在誤差值，

圖2 傳感器節(jié)點初始分布及等高線模型Fig.2 Distribution of sensors node initial and equal altitudes line model

Δx；Δy分別表示信標(biāo)節(jié)點構(gòu)建成質(zhì)心坐標(biāo)值與未知節(jié)點真實值之間的誤差。f（x，y）表示未知節(jié)點與信標(biāo)節(jié)點之間距離，如下

從數(shù)學(xué)角度而言，只有公式2知道了2個信標(biāo)節(jié)點坐標(biāo)和距離公式，在滿足滿秩的情況下，一定能夠求解出未知節(jié)點的坐標(biāo)，然而實際上，由于節(jié)點本身的限制，比如計算能力，通信干擾，使得實測數(shù)據(jù)中坐標(biāo)以及距離都存在一定的誤差，因而采用公式2進(jìn)行求解帶來一定的誤差，導(dǎo)致定位精度較低。泰勒級數(shù)的實質(zhì)是采用切線逼近方式求解方程的解，本文擬采用泰勒級數(shù)對距離公式進(jìn)行變換求解。多元泰勒級數(shù)展開形式見公式3，其中第二行表示拉格朗日余項。

對公式2在未知節(jié)點真實坐標(biāo)處X（xest，yest），用多元泰勒級數(shù)展開，公式2分別對x，y求一階偏導(dǎo)數(shù)，

則公式2在未知節(jié)點X（xest，yest）處的泰勒級數(shù)展開如下，

公式5中，右側(cè)兩項分別表示如下

3 遺傳算法下節(jié)點自定位及優(yōu)化

3.1 優(yōu)化設(shè)計

遺傳算法是是一種高效、并行、全局搜索的方法，對于復(fù)雜的優(yōu)化問題無需建模和進(jìn)行復(fù)雜運算，只需要利用遺傳算法的算子就能尋找到問題的最優(yōu)解或滿意解。采用遺傳算法對節(jié)點自定位進(jìn)行優(yōu)化是目前研究節(jié)點自定位方面的一個研究方向，縱觀現(xiàn)有的研究采用遺傳算法的傳感器網(wǎng)路節(jié)點自定位文獻(xiàn)來看，針對陸地上的節(jié)點自定位的研究比較多[1,3,7,9]，由于陸地環(huán)境和水下環(huán)境不同，陸地上的現(xiàn)有的研究設(shè)計環(huán)境及優(yōu)化不一定適合于水下，而針對水下傳感器節(jié)點的自定位比較少，水下的環(huán)境比較復(fù)雜，影響節(jié)點自定位的因素也很多，本文主要考慮二維空間的情況。

在水下某區(qū)域布置傳感器節(jié)點，假設(shè)節(jié)點能夠通過某種方式布置在同一的深度位置，節(jié)點位置不隨著洋流，擾動等因素發(fā)生變化，節(jié)點之間能夠水聲方式進(jìn)行有效的通信，信標(biāo)節(jié)點能夠通過某種方式(如通過浮標(biāo)等)獲得自身的各種信息，從大規(guī)模布置節(jié)點，信標(biāo)節(jié)點和浮標(biāo)的制作，從經(jīng)濟(jì)等角度來看，目前還不適合大規(guī)模布置所有節(jié)點都是信標(biāo)節(jié)點，因而少部分信標(biāo)節(jié)點大部分為未知節(jié)點是目前現(xiàn)有的方式之一[10-14]，將該模型簡化成在一個二維空間中，已知若干節(jié)點坐標(biāo)，對其余一些節(jié)點進(jìn)行坐標(biāo)的位置的確定。遺傳算法的最重要的特點之一是，僅僅關(guān)注適應(yīng)度函數(shù)本身，而對具體是什么樣的問題不作關(guān)心，將水下二維節(jié)點自定位問題簡化，等效，然后可以用遺傳算法對其進(jìn)行尋優(yōu)。按公式（1-7）取適應(yīng)度函數(shù)如下：

步驟設(shè)計

開始，節(jié)點初始化，信標(biāo)節(jié)點相互之間通過交換信息，獲知各自在網(wǎng)絡(luò)中的位置等信息，然后向外界不斷廣播自身的信息，未知節(jié)點接收信息。

1）隨機產(chǎn)生NIND個個體作為初始種群，每個個體為二維向量，每個二維個體含有PRICE個基因位，因而初始種群構(gòu)成了NIND*(2*PRICE)大小的矩陣；二維向量代表了未知節(jié)點的坐標(biāo)估計位置；

2）初始種群轉(zhuǎn)換為十進(jìn)制，并按公式10計算每一個個體的適應(yīng)度函數(shù)值；

3）對函數(shù)值按適應(yīng)度大小進(jìn)行排序；適應(yīng)度較高的個體被遺傳到下一代的概率較大，適應(yīng)度較低的個體被遺傳到下一代的機會較少，概率為GGAP；對個體配對，按概率Pc進(jìn)行交叉操作，按概率Pm進(jìn)行變異操作，交叉操作受γ參數(shù)控制；

4）重插入子種群產(chǎn)生新的NIND個個體，計算目前種群適應(yīng)度函數(shù)；

5）判斷，是否滿足收斂條件，不滿足則跳轉(zhuǎn)到步驟2），滿足則輸出最優(yōu)解。

4 結(jié)果及分析

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

圖3 均值和最佳解Fig.3 Average and the best solution

圖4 進(jìn)化到第八代的目標(biāo)函數(shù)值Fig.4 The values of objective function in eighth generation

觀察圖3和圖4，可以看出，均值在不斷的變小，表明在不斷尋優(yōu)過程中，解不斷向最佳情況變化，采用泰勒級數(shù)能夠逼近最優(yōu)解。

為進(jìn)一步研究參數(shù)對結(jié)果的影響，分別改變變異概率以及交叉概率。

圖6 均值和最佳解Fig.6 Average and the best solution

圖5和圖6是在代溝不變的情況下，分別改變變異和交叉概率得到的，其中圖5的變異和交叉概率分別是0.1和0.5，圖6的分別是0.01和0.1，對比圖3、圖5和圖6可以看出，圖6最佳解幾乎沒有什么變化，也就是說在變異概率和交叉概率很小的情況下，很難尋找到最優(yōu)解，從而使得節(jié)點定位的精度變低。從以上各圖可以得出，采用泰勒級數(shù)開展方式，并用遺傳算法進(jìn)行尋優(yōu)迭代，能夠求出最佳解，進(jìn)而能夠?qū)ξ粗?jié)點進(jìn)行定位。

遺傳算法本身只對適應(yīng)度函數(shù)感興趣，對定位的研究提煉成適應(yīng)度函數(shù)以后，沒有再考慮節(jié)點實際情況，本文的最佳目標(biāo)函數(shù)解是0，從理論上表明遺傳算法能夠?qū)?jié)點定位起到優(yōu)化作用，但到實際應(yīng)用中去，還有一些工作要做，這也是下一步研究的方向。

5 結(jié)束語

水聲傳感器網(wǎng)絡(luò)是海洋戰(zhàn)略中重要的一環(huán)，節(jié)點自定位則是水聲傳感器網(wǎng)絡(luò)節(jié)點自定位的關(guān)鍵技術(shù)之一。本文采用泰勒級數(shù)對節(jié)點間的距離公式進(jìn)行逼近求解，并用遺傳算法對其進(jìn)行優(yōu)化，仿真結(jié)果表明，在不額外增加硬件設(shè)備的條件下，不考慮信標(biāo)節(jié)點與未知節(jié)點的通信距離約束情況，能夠?qū)崿F(xiàn)對未知節(jié)點的定位誤差的尋優(yōu)求解。

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

[2]SHENG Xiao-hong,HU Yu-hen.Maximum likelihood multiple-source localization using acoustic energy measurements with wireless sensor networks[J].IEEE Transactions on Signal Processing,2005,53(1):44-53.

[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]AKYILDIZ I F,POMPILI D,MELODIA T.Underwater acoustic sensor networks:research challenges[J].Ad Hoc Networks,2005,3(3):257-279.

[5]石琴琴.無線傳感器網(wǎng)絡(luò)節(jié)點自定位系統(tǒng)及其算法研究[D].上海:上海交通大學(xué),2009.

[6]王馭風(fēng),王 巖.基于矢量的無線傳感器網(wǎng)絡(luò)節(jié)點定位綜合算法[J].通信學(xué)報,2008,29(11):227-231.

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

[8]CHENG W,TEYMORIAN A Y,MA L,et al.Underwater localization in sparse 3d acoustic sensor networks 2008.IEEE.

[9]王 懌.水下傳感網(wǎng)時鐘同步與節(jié)點定位研究[D].武漢:華中科技大學(xué),2009.

[10]AKYILDIZ I F,POMPILI D,MELODIA T.Challenges for efficient communication in underwater acoustic sensor networks[J].ACM Sigbed Review,2004,1(2):3-8.

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

[12]CUI J H,KONG J,GERLA M,ET AL.The challenges of building scalable mobile underwater wireless sensor networks for aquatic applications[J]..IEEE NETWORK,2006,20(3):12.