水下聲學傳感器網絡節點定位算法及自組織過程研究*

梁 玥，劉 忠，夏清濤

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

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

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

本文在上述工作的基礎上，針對水下環境中錨節點稀疏的現象，給出了分布式的節點定位算法以及配合該定位算法的分布式并發數據傳播算法。

1 分布式節點定位算法

1．1 測距公式

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

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

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

1．2 TERRAIN定位算法

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

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

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

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

圖1 局部坐標系

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

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

2 自組織數據傳播算法

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

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

2．1 基本算法

現設網絡中存在M個錨節點和N個普通節點，錨節點與普通節點單獨編號;初始時刻所有節點都處于W_PING狀態。每一個節點要建立3個表:

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

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

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

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

圖2 分布式數據傳播算法節點狀態機

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

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

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

圖3 數據傳播算法的序列圖

2．2 沖突解決策略

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

圖4 沖突解決策略

3 仿真試驗

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

圖5 節點真實位置與估計位置

圖6 節點定位算法定位誤差曲線

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

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

圖8 定位誤差與錨節點數量、通信半徑以及節點數量的關系

4 結論

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

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

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

[3]于宏毅，李歐，張效義．無線傳感器網絡理論、技術與實現[M]．2009．

[4]張宏滔，陸佶人，童峰．一種用于水聲通信網的多址介入協議[J]．電路與系統學報，2004，9(3):46 －48．

[5]王靜，陳建峰，張立杰，等．水下無線傳感器網絡[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]羅亞松，劉忠，劉愛平．實現水聲通信網純距離節點定位自組織研究[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]廖先林，耿娜，石凱．無線傳感器網絡節點自身定位算法[J]．東北大學學報，2007，6(6):801 －804．

[10]劉克中．分布式無線傳感器網絡節點定位算法[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．