梁 玥，劉 忠，夏清濤

(海軍工程大學電子工程學院，武漢430033)

隨著網(wǎng)絡信息技術的快速發(fā)展、海洋資源開發(fā)步伐的加快以及海洋重要戰(zhàn)略地位的日益彰顯，建立水下聲學傳感器網(wǎng)絡(UASNs:Underwater Acoustic Sensor Networks)已成為各國研究的重點問題之一?？梢酝ㄟ^將微型通信節(jié)點布置在海底，或通過飛機、艦艇和潛艇隨機布撒在一定深度的海區(qū)，自組織的形成水下傳感器網(wǎng)絡，以實現(xiàn)海洋環(huán)境監(jiān)測、資源開發(fā)、軍事作戰(zhàn)等眾多的功能。

節(jié)點定位問題是UASNs的一個重要研究內容，可以分為基于距離的定位算法以及基于估計距離的定位算法[1－3]。利用節(jié)點位置信息，可以明確每個節(jié)點的身份，根據(jù)路由選擇算法建立路由表，明確節(jié)點之間所需的發(fā)射功率以及完成目標發(fā)現(xiàn)和跟蹤的功能[4]。使用GPS定位方法是一種獲得節(jié)點位置信息的簡單方法，但是由于節(jié)點數(shù)目較多，為每個節(jié)點安裝GPS定位系統(tǒng)將導致成本的增加，另外，由于GPS系統(tǒng)在有遮擋物的條件下無法完成定位，在水下采用該方法是不合適的，因此在實際水下環(huán)境中，明確自身位置的節(jié)點數(shù)量較少。在以往的研究中，文獻[5]指出水下節(jié)點定位問題是水下傳感器網(wǎng)絡設計面臨的諸多難題之一;文獻[6]綜述了哪些現(xiàn)有的WSNs中的節(jié)點定位算法可以應用于水下環(huán)境，但并沒有分析在水下環(huán)境中具體算法的性能;文獻[7]對水下環(huán)境節(jié)點定位和自組織過程進行了深入的研究，提出了一種用于網(wǎng)絡自組織的集中式數(shù)據(jù)傳播算法;文獻[8]針對水下環(huán)境通信沖突嚴重的問題，提出了基于鄰居節(jié)點喚醒機制的MAC協(xié)議。

本文在上述工作的基礎上，針對水下環(huán)境中錨節(jié)點稀疏的現(xiàn)象，給出了分布式的節(jié)點定位算法以及配合該定位算法的分布式并發(fā)數(shù)據(jù)傳播算法。

1 分布式節(jié)點定位算法

1．1 測距公式

由于基于距離信息的定位算法與基于估計距離信息的定位算法相比精度更高[9]，因此可以采用4種測距方法:AOA、RSSI、TDOA和TOA。由于水下環(huán)境的特點，通常采用聲音信號作為主要的傳播手段，因此我們采用基于TOA的方法測量節(jié)點之間的相對距離，測距公式如式(1)～式(3)所示。

式(1)中，D表示節(jié)點之間的距離，Tproc表示聲信號在水聲信道中的傳播時延，由式(3)計算;vs表示聲波在水中的傳播速度，由式(2)計算;式(2)中，P表示水溫，s表示鹽度，h表示深度;式(3)中，Tsig表示接收節(jié)點完成數(shù)據(jù)接收的時刻Tc與數(shù)據(jù)包中保存的發(fā)送時戳信息Tp的差值，由于水聲信道傳輸速率比較低，數(shù)據(jù)包傳播延遲Ttran在計算Tproc不能忽略，Lp表示數(shù)據(jù)包的長度，Rt表示數(shù)據(jù)傳輸速率。

由于TOA方法利用了時間信息，因此各個節(jié)點之間要進行時間同步，時間同步的精度影響測距精度，但是考慮到水聲信號傳播速度比起電磁波來說要慢得多，并且水聲通信網(wǎng)各節(jié)點的間距較大，從整體把握拓撲結構的目的出發(fā)，系統(tǒng)對時間同步精度的要求不大，當前電子精振的精度完全可以勝任，因此在水聲通信網(wǎng)中利用算法簡單的TOA方法完成測距是方便可行的。

1．2 TERRAIN定位算法

根據(jù)前面分析，在水下環(huán)境中不能為每個節(jié)點安裝GPS定位系統(tǒng)，因此只有少量的節(jié)點可以獲得自身的地理位置信息，這類節(jié)點通常稱為錨節(jié)點，錨節(jié)點可由已知位置信息的艦艇、潛艇或具有特殊功能的節(jié)點擔任。在錨節(jié)點較少的情況下，如不采取措施就進行定位，會導致可定位的節(jié)點比例較低。

TERRAIN算法是適用于錨節(jié)點較少情況下的定位算法，現(xiàn)以一個錨節(jié)點N1為例，其定位算法的主要步驟如下:

步驟1建立坐標系 如圖 1所示，N1為原點，其坐標為(0，0)，第一個與N1通信的節(jié)點N2的連線作為X軸，其坐標為(DN1N2，0);Y軸定義為以沿X軸逆時針旋轉90°所得的方向線;

步驟2確定參考節(jié)點坐標 在N1和N2的鄰接表中，選擇一個同時與N1和N2進行通信，并且與其距離之和最大的節(jié)點作為 N3，其位置坐標如式(4)所示;

圖1 局部坐標系

步驟3確定其它節(jié)點的相對坐標 以上述三個參考節(jié)點的坐標為基礎，利用三邊測量法計算其它節(jié)點的相對坐標，進而獲得與該錨節(jié)點的距離。

實際上，上述步驟是在所有錨節(jié)點同時進行的，節(jié)點可以獲得與多個錨節(jié)點的距離值。設節(jié)點的坐標為(x，y)，網(wǎng)絡中存在k個錨節(jié)點，坐標為(xi，yi)i=1，2，…，k，節(jié)點與錨節(jié)點的距離為 DNi，i=1，2，…，k，當一個節(jié)點獲得多個與錨節(jié)點的距離值時，可以利用最小二乘法如式(5)～式(7)所示，計算出節(jié)點的地理位置為X=(ATA)－1ATB。

2 自組織數(shù)據(jù)傳播算法

為實現(xiàn)節(jié)點之間的定位，必須在網(wǎng)絡自組織形成過程中，完成節(jié)點鄰接信息表的建立以及各節(jié)點信息的匯集工作，因此，節(jié)點之間需要完成大量的通信來交互信息。但是，此時網(wǎng)絡處于無序狀態(tài)，節(jié)點間的通信沖突將對自組織形成所需的時間和效果產(chǎn)生重大影響。在以電磁波形式通信的無限傳感器網(wǎng)絡中，由于電磁波傳播速度快，且數(shù)據(jù)傳輸率高，通信沖突帶來的影響不大，可以采用廣播和競爭重發(fā)機制實現(xiàn)節(jié)點信息的傳遞與收集，這也是當前網(wǎng)絡研究中普遍采用的方法。但是在水聲環(huán)境中，由于水聲通信傳輸率低(信道帶寬有限)、數(shù)據(jù)包尺寸大(包含大量對惡劣信道修正的訓練序列)等不利因素，大大增加了通信沖突發(fā)生的概率，同時聲信號傳播速度慢的特點也增大了數(shù)據(jù)重傳的代價，這些都導致了傳統(tǒng)的競爭和重發(fā)機制在水聲通信網(wǎng)自組織形成過程中的低效率。對于拓撲結構較簡單的水聲通信網(wǎng)，由于大多數(shù)節(jié)點只能與其它某一個節(jié)點通信(鏈式結構)，廣播和競爭重發(fā)機制所帶來的通信沖突不嚴重，可以較好的運行;但是對于穩(wěn)健性較高的復雜拓撲結構網(wǎng)絡來說，嚴重的通信沖突將大大影響廣播的順利進行，甚至還會出現(xiàn)由于信息收集不完全，導致無法實現(xiàn)網(wǎng)絡自組織形成的情況。

鑒于目前對水聲通信網(wǎng)絡自組織過程研究較少的情況，本文提出了一種分布式的數(shù)據(jù)傳播算法，以配合定位算法的完成;由于分布式算法在執(zhí)行過程中會在某一節(jié)點處產(chǎn)生接收沖突問題，因此本文也對解決通信沖突的相關問題進行了研究。

2．1 基本算法

現(xiàn)設網(wǎng)絡中存在M個錨節(jié)點和N個普通節(jié)點，錨節(jié)點與普通節(jié)點單獨編號;初始時刻所有節(jié)點都處于W_PING狀態(tài)。每一個節(jié)點要建立3個表:

對于判別網(wǎng)絡D，原來是接收圖像，輸出打分D（），而這里不僅接收圖像，還需接收圖像和文本描述特征φ（t），因為除了G生成的圖像之外，還要保證G生成的圖像不僅與輸入的圖像相匹配，與文本描述也要匹配。最后輸出打分 G（，x，φ（t））。

(1)鄰接信息表Mi包括相鄰節(jié)點的ID號、與相鄰節(jié)點的距離;

(2)本地數(shù)據(jù)表Li節(jié)點的局部坐標、全局坐標以及錨節(jié)點坐標;

(3)節(jié)點狀態(tài)表Si由M個元素組成的集合表示;當節(jié)點在第i個錨節(jié)點為原點的局部坐標系下計算出局部坐標后，集合中相應位的元素置為1，否則置為0。節(jié)點狀態(tài)轉換圖如圖2所示。

圖2 分布式數(shù)據(jù)傳播算法節(jié)點狀態(tài)機

步驟1確定參考節(jié)點1 初始時刻將M個錨節(jié)點分別作為參考節(jié)點1，使其進入PING狀態(tài)，N個普通節(jié)點皆處于W_PING狀態(tài);參考節(jié)點1向其它(M+N－1)個節(jié)點發(fā)送PING_RTS幀，包括該幀建立的時間和參考節(jié)點1的坐標;利用在規(guī)定時間內是否收到相應節(jié)點的反饋數(shù)據(jù)來判斷是否連通。當鄰接信息表未建立時，如果一個節(jié)點收到了參考節(jié)點1的PING_RTS幀，則可計算與參考節(jié)點1之間的距離，更新自己的鄰接信息表，記錄參考節(jié)點1的坐標;并向其反饋PING_CTS幀，包括建立PING_CTS幀的時間。如果參考節(jié)點1在規(guī)定時間內沒有收到其它節(jié)點反饋的PING_CTS幀，則認為不能與該節(jié)點連通。當鄰接關系建立后，參考節(jié)點1根據(jù)鄰接關系表，選定與之距離最大的一個節(jié)點作為X軸上的參考節(jié)點2，并向其發(fā)送數(shù)據(jù)幀SET，數(shù)據(jù)幀中包含被選定的信息以及鄰接關系表;而后進入COMPUTE狀態(tài)，設置自己在該坐標系下的坐標;完成上述操作后，轉入END狀態(tài)。

步驟2確定參考節(jié)點2 參考節(jié)點2由W_PING狀態(tài)進入PING狀態(tài)，向其它(M+N－1)個節(jié)點發(fā)送PING_RTS幀，根據(jù)在規(guī)定時間內是否接受到其它節(jié)點的反饋PING_CTS來更新鄰接信息表;確定自身的局部坐標，更新本地數(shù)據(jù)表，同時將狀態(tài)表中的相應位置為1;比較自身的鄰接信息表和參考節(jié)點1的鄰接信息表，從中選出到參考節(jié)點1和參考節(jié)點2距離之和最大的點作為參考節(jié)點3，并向其發(fā)送包含選定信息的數(shù)據(jù)幀SET;而后進入COMPUTE狀態(tài)，設置自身在該坐標系下的坐標，完成上述操作后，進入END狀態(tài)。

步驟4節(jié)點計算自身坐標 當節(jié)點接收到三個局部坐標已知的節(jié)點的數(shù)據(jù)幀時，該節(jié)點進入COMPUTE狀態(tài);根據(jù)三邊測量法計算出自身坐標，并將狀態(tài)表中的相應位置置為1;同時向其它節(jié)點發(fā)送PING_RTS幀，根據(jù)規(guī)定時間內是否收到PING_CTS幀，更新鄰接信息表;完成上述操作后，進入END狀態(tài)。當網(wǎng)絡中的所有節(jié)點計算出局部坐標或大于最大計算時間時，算法結束。數(shù)據(jù)傳播過程的序列圖如圖3所示。

圖3 數(shù)據(jù)傳播算法的序列圖

2．2 沖突解決策略

在基于上述算法的數(shù)據(jù)傳播過程中，會存在一定的數(shù)據(jù)沖突，特別是在當多個節(jié)點向同一個節(jié)點發(fā)送信息時，會在接收節(jié)點處產(chǎn)生接收－接收沖突問題[11－12]。在這種情況下，可以通過在每一個節(jié)點傳輸持續(xù)時間的兩端增加一定的保護時間，如果發(fā)送節(jié)點的喚醒時刻與本節(jié)點的傳輸起始點或結束點之間的絕對值小于保護時間時，發(fā)送節(jié)點就需要重新選擇發(fā)送時間，以避免接受沖突的發(fā)生。沖突的避免過程如圖4所示，其中S1、S2為發(fā)送節(jié)點，R為接收節(jié)點，節(jié)點S2重新選擇了發(fā)送時間，避免了沖突的產(chǎn)生。

圖4 沖突解決策略

3 仿真試驗

設節(jié)點均勻分布在15 000 m×15 000 m的區(qū)域中，包含200個普通節(jié)點，錨節(jié)點的比例為10%，節(jié)點的通信半徑采用實物節(jié)點的真實通信半徑3 km，設節(jié)點位置誤差服從均值為0、均方差為0．01 m的高斯分布，節(jié)點之間的測量距離服從均值為0、均方差為0．0001 m的高斯分布，共進行50次仿真試驗，定義節(jié)點的定位誤差為:共進行J次網(wǎng)絡仿真，節(jié)點的平均定位誤差為其中N為節(jié)點的個數(shù)，試驗結果如圖5和圖6所示;由于水下環(huán)境中錨節(jié)點個數(shù)較少，這里減少錨節(jié)點個數(shù)至5，同時減少通信半徑至1 km，其它條件不變，仿真結果如圖7所示;定位誤差與錨節(jié)點數(shù)、通信半徑以及節(jié)點個數(shù)的關系如圖8所示。

圖5 節(jié)點真實位置與估計位置

圖6 節(jié)點定位算法定位誤差曲線

圖7 錨節(jié)點較少時的真實位置與估計位置

試驗表明，在實際水下環(huán)境錨節(jié)點較少的情況下，上述兩種方法配合可以完成節(jié)點定位過程，并且定位誤差在3%以下。進一步提高錨節(jié)點比例、通信半徑，節(jié)點定位誤差曲線可以下降收斂到某一精度。當其它條件不變、進一步提高節(jié)點個數(shù)的條件下，節(jié)點定位誤差曲線在初始階段下降，然后有可能會出現(xiàn)上升的情況。這是由于節(jié)點個數(shù)增加，網(wǎng)絡中節(jié)點密度增大，未定位節(jié)點可參考的已定位節(jié)點個數(shù)增加，可參考的信息量增加，但是同時，解算過程中A矩陣奇異的可能性也增加，因此會存在網(wǎng)絡中節(jié)點個數(shù)越多，節(jié)點定位誤差曲線反而上升的現(xiàn)象。

圖8 定位誤差與錨節(jié)點數(shù)量、通信半徑以及節(jié)點數(shù)量的關系

4 結論

本文給出了一種分布式的節(jié)點定位算法和在節(jié)點自組織過程中用到的數(shù)據(jù)傳輸算法。仿真試驗驗證了上述算法配合完成節(jié)點定位的可行性。在未來的研究中，關于環(huán)境因素對算法的影響還需要進行進一步的深入研究。

[1]王福豹，史龍，任豐原．無線傳感其網(wǎng)絡中的自身定位系統(tǒng)和算法[J]．軟件學報，2005，16(5):857 －868．

[2]孫利民，李建，陳渝，等．無線傳感器網(wǎng)絡[M]．2005．

[3]于宏毅，李歐，張效義．無線傳感器網(wǎng)絡理論、技術與實現(xiàn)[M]．2009．

[4]張宏滔，陸佶人，童峰．一種用于水聲通信網(wǎng)的多址介入?yún)f(xié)議[J]．電路與系統(tǒng)學報，2004，9(3):46 －48．

[5]王靜，陳建峰，張立杰，等．水下無線傳感器網(wǎng)絡[J]．聲學技術，2009，28(1):89 －95

[6]Chandrasekhar V，Winston K S，Yoo Sang Choo．Location in Underwater Sensor Networks Survey and Cha-Llenges[C]//WUWNet’2006，33－40

[7]羅亞松，劉忠，劉愛平．實現(xiàn)水聲通信網(wǎng)純距離節(jié)點定位自組織研究[J]．武漢理工大學學報，2009，31(1):110 －115

[8]Nam Yeol Yun，Hui Jin Cho，Soo Hyun Park．Neighbor Nodes Aware MAC Sche-Duling Scheme in Underwater Acoustic Sensor Networks[J]．International Conference on Computational Science and Engineering，2009:982 －987

[9]廖先林，耿娜，石凱．無線傳感器網(wǎng)絡節(jié)點自身定位算法[J]．東北大學學報，2007，6(6):801 －804．

[10]劉克中．分布式無線傳感器網(wǎng)絡節(jié)點定位算法[D]．武漢:華中科技大學，2007．

[11]Park M K，Rodoplu V．UWAN-MAC:An Energy-Efficient MAC Protocol for Underwater Acoustic Wireless Sensor Network[J]．IEEE Journal of Oceanic En-gineering，2007，23(3):

[12]Affan Syed，John Heidemann．T-Lohi:A New Class of MAC Pro-Tocols for Underwater Acoustic Sensor Networks[C]//Por of IEEE Inform，231－235．