UASN中改進的錨點定位報文傳輸方案

林奕水， 何震葦

(1. 廣東農工商職業技術學院，廣東 廣州 510507；2. 中國電信股份有限公司 廣東研究院，廣東 廣州 510507)

?

UASN中改進的錨點定位報文傳輸方案

林奕水1， 何震葦2

(1. 廣東農工商職業技術學院，廣東 廣州 510507；2. 中國電信股份有限公司 廣東研究院，廣東 廣州 510507)

水下聲學傳感器網絡具有傳輸延時較長、數據速率較低、傳輸損耗較大等特點，影響著現有定位算法的報文傳輸效率。針對水下聲學傳感器網絡中現有定位算法在報文傳輸效率方面的不足，提出了一種改進的定位報文傳輸方案。首先，已知錨點的相對位置及其最大傳輸范圍后，分析了定位時的無沖突報文傳輸條件，然后定義定位任務時間最小化問題，并證明該問題可以獲得最優解。在此基礎上，提出兩種基于調度的低復雜度求解算法。最后，通過多次仿真實驗來比較該改進算法與OCSMA等當前水下MAC協議及傳統的時隙方法的性能，實驗結果表明本文算法的性能達到準最優水平，且遠優于TDMA和OCSMA等其他當前算法。

水下聲學傳感器網絡； 定位； 錨點； 報文傳輸； 最優解

0 引 言

為了滿足水下應用的需要，水下聲學傳感器網絡[1](Underwater Acoustic Sensor Network, UASN)負責測量水溫、化學物密度、海床形狀等參數。如果這些數據沒有附上時間和測量位置便沒有意義，所以定位問題是UASN的重要問題，促使人們對水下定位展開大量研究[2-3]。雖然可以在定位時使用當前的無線傳感器網絡的MAC(Media Access Control)協議和算法，但是鑒于UASN的獨特屬性，比如傳輸延時較長、數據速率較低、傳輸損耗較大，導致使用當前無線傳感器網絡的MAC協議和算法的效率不高[4-5]。

梁玥等[6]針對UASN中錨節點稀少的問題，給出了一種分布式的水下節點自定位算法。為配合定位算法的完成，出了一種分布式的并發數據傳播算法，并針對該數據傳播算法中存在的通信沖突問題，給出了沖突解決策略。文獻[7]提出了有序調度協議(OCSMA)來廣播錨點報文。該協議中有一個協調器根據關于錨點相對位置的完整信息來確定傳輸序列，然后向錨點通知所生成的序列。此時，錨點根據指定序列逐個進行報文傳輸。然而，該協議對定位任務來說并不是最優協議，因為它不支持在網絡中同時傳輸數據。為了克服這一問題，文獻[8]提出了一種單跳多對多廣播傳輸調度協議(AAB-MAC)。該協議的目標是在保證不發生沖突的前提下盡量減小多對多傳輸周期。雖然AAB-MAC優于OCSMA，但它無法用于定位任務，一方面是因為我們不知道所有水下傳感器節點的位置，另一方面是因為只對錨點使用AAB-MAC協議會導致傳感器節點沖突。當前還有其他多種基于調度的水下網絡MAC協議[9-13]。但是，它們著眼于單播報文交換，沒有考慮基于定位信標的無沖突廣播，因此不適用于水下網絡定位任務。

本文研究錨點定位報文的調度，利用錨點的位置信息及傳輸范圍信息來盡量降低定位的時間。所有錨點傳輸完報文后，定位過程才算結束。每個錨點報文中的信息包括錨點ID、錨點位置、及報文傳輸時間。我們定義定位任務時間最小化問題，并證明該問題可以獲得最優解。然后，提出兩種基于調度的低復雜度求解算法(L-MACs)。最后，通過多次仿真驗證本文算法的最優性能及相對其他當前算法的優越性。

1 網絡模型

假設水下傳感器網絡有N個位于水面的錨點(如果位置信息已知，則可位于任何地方)，且最大傳輸范圍為Rm，在錨點的覆蓋范圍內有M個水下傳感器節點。假設水面錨點配備了GPS設備、無線電(或衛星)和聲學解調器。此外，融合中心通過無線解調器可以收集錨點信息。另一方面，沒有關于水下傳感器節點位置的先驗信息，且傳感器可能位于監測區域的任何位置。融合中心負責對錨點的定位報文傳輸進行調度，且每個報文的時間為tp。我們的目標是使定位時間最小化，并避免任何水下傳感器節點在接收報文時發生沖突。為此，融合中心在每個錨點傳輸報文前為每個錨點i設置一個等待時間wi。

為了避免任何潛在的報文沖突，我們必須解決的一個問題是使最大等待時間最小化。如果一個傳感器節點有兩個甚至更多個傳輸報文互相重疊，則認為發生沖突。但是因為傳感器節點可能位于媒介中的任何位置，所以來自錨點的傳輸報文可能在2個錨點傳輸范圍的相交區域任一位置發生沖突。此時，如圖1所示，即使2個錨點沒有位于聲學傳輸范圍內，它們也有可能在網絡中發生沖突。為了避免沖突問題，引入無沖突錨點概念。簡單地講，如果兩個錨點的距離小于最大傳輸范圍的2倍，則稱這2個錨點為沖突高發相鄰錨點，發生沖突的概率較大。在下一小節，將證明如何改變等待時間以避免發生錨點沖突問題。

圖1 2個高危沖突錨點的示意圖

1.1 無沖突錨點

假設有兩個錨點i和j，相距dij，等待時間分別為wi和wj且wi>wj。當它們滿足如下三個條件時，則上述兩個錨點無沖突：

條件1：當2個錨點間的距離大于2R時，那么無論需要等待多少時間，它們的傳輸報文均不會發生沖突，因為它們的傳輸范圍沒有相交區域。我們將這2個錨點稱為嚴格距離相關無沖突節點。

條件2：假設水下媒介的聲速為c。如果兩個等待時間之差為R/c+tp，則無論節點間距如何，2個節點的傳輸報文也不會發生沖突。我們將這2個錨點稱為嚴格時間相關無沖突節點。

(1)

總體來說，wi未必大于wj，那么當錨點j的等待時間已知時為了保證定位報文不發生傳輸沖突，則wi必須在下述邊界之外：

(2a)

(2b)

圖2 當R

條件4：如果wi-wj>tp+dij/c，則錨點i和j為無沖突錨點，圖3為wi-wj最小值情形。當dij

(3)

圖3 dij

如上文所示，wi未必大于wj，那么當錨點j的等待時間已知時為了保證定位報文不發生傳輸沖突，則wi必須在下述邊界之外：

(4a)

(4b)

在明確了無沖突報文傳輸的相關條件后，我們將優化問題定義如下：

s.t. (1)wi≥0,fori=1,2,…,N

(5)

其中，式(1)表示我們無法在負數時間傳輸報文；式(2)表示條件1～4的融合。

從條件3和4中可以發現，為了保證無沖突報文傳輸，設置一個錨點的等待時間后將會對相鄰無沖突錨點的等待時間帶來約束。這些約束不僅與錨點報文傳輸之后的時間有關，還與錨點報文傳輸之前的時間有關。這一點對于確定式(5)的最優解非常重要。

1.2 TDMA系統下的問題定義

在TDMA系統下，如每個時隙的時間長度設為ts=tp+R/c，則有R/c→0，于是式(5)優化函數等價為定位報文無沖突傳輸時使時隙數量最小化。因此，問題式(5)可建模為TDMA廣播調度問題[14]。如文獻[9]所示，用最小數量的時隙實現報文調度是NP難題。然而，R/c→0時廣播問題的解是可實現定位任務最小化的最優解。當R/c≠0時，該解不是最優解，但仍然可以用于定位報文調度。把可以實現廣播調度問題時隙數量最小化的最優和準最優算法稱為時隙或TDMA算法。在無線傳感器網絡中，波速為光速，傳輸時間可以忽略，因此時隙算法性能較優。然而，水下通信的傳輸時延很大，有時甚至大于報文長度，對定位報文來說更是如此。此時，時隙算法的效率較低，需要開發其他算法。

2 最優解

首先討論如何獲得時隙方法的最優解，然后以此為基礎，闡述如何對該最優解進行拓展以確定本文問題的最優解。如先前所述，以嚴格距離相關無沖突錨點和嚴格時間相關無沖突錨點概念為基礎的時隙調度是NP難題，可看成是混合整數線性規劃問題(MILP)。其中，最優解(可能唯一)存在于N!個可能解中，通過窮盡搜索可以獲得。已知錨點序列后，給出如何將錨點分配給最小數量的時隙可以避免沖突。以此已知序列為基礎，從第1個錨點開始，將其分配給第1個時隙。然后，移到第2個錨點，將其分配給考慮了先前調度的錨點之后也不會導致沖突的最早時隙。然后，重復相同步驟，直到最后一個錨點調度完畢。最后，計算使用時隙的數量，在所有N!個可能序列中，選擇時隙數量最少的序列。

為了獲得本文問題的最優解，遵守相同的步驟。然而，此時需要確定錨點無法傳輸報文的時間長度(考慮了先前被調度的錨點后可能導致的沖突)。如果已知有序序列后，一個錨點想要傳輸報文，則它在知道了先前被調度錨點的等待時間后計算可用于傳輸報文且不會導致沖突的最早可用時間段(見條件1、3、4)。重復這一步驟，直到最后一個錨點被調度完。最后，比較所有錨占序列(N!個可能序列)的最大等待時間(wmax)，選擇wmax最小的最優次序。我們將可以求解式(5)優化函數的所有算法稱為L-MAC算法。

3 本文算法

最優解的復雜度(不使用啟發式策略)為N!，當錨點數量較大時可行性很低。現提出一種復雜度分別為N和N2的兩種啟發式算法，可用于不同場景。

3.1 L-MAC-IS

L-MAC-IS算法的步驟見表1。在該算法中，所有等待時間在初始步驟中設置為0。算法在開始時調度一個經過預先設置的隨機錨點(比如第I個錨點)。因此，該錨點的等待時間設置為0。當錨點的等待時間設置完畢后，將從調度任務中刪除。以此固定的等待時間為基礎，檢測先前被選擇的錨點的無沖突相鄰錨點，改變它們的等待時間，以保證網絡中不會發生沖突(基于條件1～4的無沖突錨點)。然后，從未經過調度的錨點中選擇等待時間最短的錨點，重復上述步驟，直到所有錨點的等待時間均被確定為止。有可能有兩個或更多個錨點的最小等待時間相同。此時，選擇序號最小的錨點。

表1 L-MAC-IS算法

3.2 最優啟動器算法

最優啟動器算法(L-MAC-BS)是L-MAC-IS算法的一種拓展。在L-MAC-BS中，對所有錨點(I=1 toN)運行L-MAC-IS，選擇可使總體調度時間最小化的錨點(最優啟動器)。該算法的步驟見表2。

表2 L-MAC-BS算法

4 性能評估

本節評估本文算法的性能，并與最優解做比較。為了驗證本文算法的優越性，還將其與OCSMA等當前水下MAC協議及傳統的時隙方法做比較。在OCSMA中不允許報文并發傳輸，只有前一錨點傳輸完畢后，后一錨點才能傳輸。可以推測，如果每個錨點在所有其他錨點的聲學傳輸范圍內，則最優OCSMA協議便是定位時間最小化問題的最優解。尋找OCSMA的最優解是個NP難題[15]。因此，針對該算法再次使用首個最優啟動器概念，并將其性能與本文算法做比較。下面圖形中每個點的計算，均是103次獨立蒙特卡洛運行結果的均值。此外，定位報文的長度為50 ms，(使用聲學解調器且數據率為1 kb/s時有50 b)，足以傳輸錨點ID、位置和傳輸時間等信息。

圖4中的方形區域有dx=dy=5c，且假設錨點均勻分布于該區域上。錨點的最大傳輸范圍為2c。這里，增加錨點的數量，然后計算定位任務的平均時間，且定義tavg=E[wmax+tp]。如圖4所示，L-MAC-BS、LMAC-1S(首先選擇序號為1的錨點)和最優解的性能非常接近；如果應用場合對復雜度要求較高，則可選擇L-MAC-1S。由于比較費時，所以對其余仿真結果我們沒有計算最優解的性能。

圖4 平均報文傳輸時間與錨點數量的變化情況

圖5給出了區域范圍確定后，最大傳輸范圍對tavg的影響。可以看出，當R增加時，嚴格距離相關無沖突錨點的數量將會下降，于是報文同時傳輸的概率下降，tavg上升。當網絡完全連通時，tavg的上升趨勢停止，如前文預測，此時OCSMA的性能與本文算法相近。

圖5 平均報文傳輸時間與錨點最大傳輸范圍的變化情況

在圖6中，給出了算法和網絡規模的變化情況。此時，當作用區域的尺寸增加時，錨點的數量也將上升，以保證單位面積的錨點數量不變。同時，當網絡面積增大時，更多節點成為嚴格距離相關無沖突節點的概率下降，節點的等待時間變長。然而，當網絡增大時，高危沖突相鄰節點的平均數量趨于一個固定值，于是時隙算法和本文算法的性能達到飽和。相反，OCSMA的性能下降，原因是錨點數量上升，總體定位時間也將上升。

圖6 算法性能與網絡規模的變化情況

5 結 語

本文定義了水下傳感器網絡的定位報文調度問題。此外，提出2種低復雜度算法，以實現定位任務的時間最小化。證明本文算法的性能達到準最優水平，且遠優于TDMA和OCSMA等其他當前算法。之后，將研究大部分水下節點不在錨點覆蓋范圍內時的定位問題。這類網絡的最優MAC協議可以看成是本文情況的一種拓展。

[1] 郭忠文, 羅漢江, 洪 鋒. 水下無線傳感器網絡的研究進展[J]. 計算機研究與發展，2010，47(3)：377-389.

[2] 魏先民. 基于多面體質心算法的水下傳感器網絡定位[J]. 計算機科學, 2012, 39(5): 102-105.

[3] Han G, Jiang J, Shu L,etal. Localization algorithms of underwater wireless sensor networks: A survey [J]. Sensors, 2012, 12(2): 2026-2061.

[4] 周 異, 陳劍波, 陳 凱, 等. 基于移動信標的大規模水下傳感器網絡節點定位[J]. 計算機應用與軟件, 2011, 28(10): 55-57.

[5] 王 彪, 李 宇, 黃海寧. 水聲傳感器網絡目標協同定位方法研究[J]. 系統仿真學報, 2009 (19): 6174-6177.

[6] 梁 玥, 劉 忠, 夏清濤. 水下聲學傳感器網絡節點定位算法及自組織過程研究[J]. 傳感技術學報, 2011, 24(3): 402-406.

[7] Van Kleunen W, Meratnia N, Havinga P J M. Scheduled MAC in beacon overlay networks for underwater localization and time-synchronization[C]//ACM, New York, 2011: 6-13.

[8] Soonchul P, Jaesung L I M. A Parallel Transmission Scheme for All-to-All Broadcast in Underwater Sensor Networks [J]. IEICE transactions on communications, 2010, 93(9): 2309-2315.

[9] Hsu C C, Lai K F, and Chou C F,etal. ST-MAC: Spatial-temporal Mac scheduling for underwater sensor networks[C]//INFOCOM 2009, IEEE. IEEE, 2009: 1827-1835.

[10] Kredo K, Djukic P, Mohapatra P. STUMP: Exploiting position diversity in the staggered TDMA underwater MAC protocol[C]// INFOCOM 2009, IEEE. IEEE, 2009: 2961-2965.

[11] 田志輝，金志剛，王 穎. 基于可變長時隙機制的水下傳感器網絡MAC協議[J]. 計算機應用，2014， 34(7):1947-1950.

[12] 金志剛，蘇毅珊，劉自鑫. 基于運動預測的水下傳感器網絡MAC協議[J]. 電子與信息學報，2013,35(3)：728-734.

[13] 洪 璐，洪 鋒，李正寶. CT-TDMA: 水下傳感器網絡搞笑TDMA協議[J]. 通信學報，2012,33(2)：164-174.

[14] Ergen S C, Varaiya P. TDMA scheduling algorithms for wireless sensor networks [J]. Wireless Networks, 2010, 16(4): 985-997.

[15] Chen Y J, Wang H L. Ordered CSMA: a collision-free MAC protocol for underwater acoustic networks[C]// OCEANS 2007. IEEE, 2007: 1-6.

Improved Localization Packets Transmission Scheme of the Anchors in UASN

LINYi-shui1,HEZhen-wei2

(1. Guangdong AIB Polytechnic College, Guangzhou 510507, China；2. Guangdong Research Institute of China Telecom Corporation Limited, Guangzhou 510507, China)

Underwater acoustic sensor network has characteristics of long transmission delay, lower data rate, high transmission loss. These characteristics affect the transmission efficiency of the existing positioning algorithm. Aiming at the deficiency, this paper proposes an improved localization packets transmission scheme of the anchor. After knowing the relative positions of the anchors and their maximum transmission range, we firstly analyze the collision free packet transmission conditions, and then define the positioning task time minimization problem, and prove that the optimal solutions can be obtained. On this basis, we propose two low complexity algorithms based on scheduling. Finally, several simulation experiments are conducted to compare the performance of the improved algorithm with the current underwater MAC protocol OCSMA and the traditional time slot method. Experimental results show that the performance of the proposed algorithm is quasi-optimal, and it is better than other current algorithms such as TDMA and OCSMA.

underwater acoustic sensor network; localization; anchor; packets transmission; optimal solution

2015-06-15

國家科技重大專項課題(2014ZX03002002)

林奕水(1980-)，男，廣東汕頭人，碩士，工程師，研究方向：水下傳感器網絡，數據收集。

Tel.：13710338768；E-mail: 44145735@qq.com

TP 391

A

1006-7167(2016)02-0089-05