謝遠黨，徐榮偉，張 華

（1.浙江海洋學院機電工程學院，浙江舟山 316004;2.舟山萬達船舶設計有限公司，浙江舟山 316101）

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

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

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

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

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

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

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

2 定位數(shù)學模型

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

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

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

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

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

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

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

公式5中，右側兩項分別表示如下

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

3.1 優(yōu)化設計

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

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

步驟設計

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

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

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

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

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

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

4 結果及分析

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

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

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

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

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

圖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ù)開展方式，并用遺傳算法進行尋優(yōu)迭代，能夠求出最佳解，進而能夠對未知節(jié)點進行定位。

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

5 結束語

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

[1]孫利民,李建中,陳 渝,等.無線傳感器網(wǎng)絡[M].北京:清華大學出版社,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)絡節(jié)點自定位系統(tǒng)及其算法研究[D].上海:上海交通大學,2009.

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

[7]曹正文,趙 健,高寶建.基于加權最小二乘法的紅外多站定位的研究[J].光子學報,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].武漢:華中科技大學,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.