林奕水， 何震葦

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

?

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

林奕水1， 何震葦2

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

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

水下聲學傳感器網(wǎng)絡； 定位； 錨點； 報文傳輸； 最優(yōu)解

0 引 言

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

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

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

1 網(wǎng)絡模型

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

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

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

1.1 無沖突錨點

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

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

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

(1)

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

(2a)

(2b)

圖2 當R

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

(3)

圖3 dij

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

(4a)

(4b)

在明確了無沖突報文傳輸?shù)南嚓P(guān)條件后，我們將優(yōu)化問題定義如下：

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

(5)

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

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

1.2 TDMA系統(tǒng)下的問題定義

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

2 最優(yōu)解

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

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

3 本文算法

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

3.1 L-MAC-IS

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

表1 L-MAC-IS算法

3.2 最優(yōu)啟動器算法

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

表2 L-MAC-BS算法

4 性能評估

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

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

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

圖5給出了區(qū)域范圍確定后，最大傳輸范圍對tavg的影響?？梢钥闯?，當R增加時，嚴格距離相關(guān)無沖突錨點的數(shù)量將會下降，于是報文同時傳輸?shù)母怕氏陆?，tavg上升。當網(wǎng)絡完全連通時，tavg的上升趨勢停止，如前文預測，此時OCSMA的性能與本文算法相近。

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

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

圖6 算法性能與網(wǎng)絡規(guī)模的變化情況

5 結(jié) 語

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

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

[2] 魏先民. 基于多面體質(zhì)心算法的水下傳感器網(wǎng)絡定位[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] 周 異, 陳劍波, 陳 凱, 等. 基于移動信標的大規(guī)模水下傳感器網(wǎng)絡節(jié)點定位[J]. 計算機應用與軟件, 2011, 28(10): 55-57.

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

[6] 梁 玥, 劉 忠, 夏清濤. 水下聲學傳感器網(wǎng)絡節(jié)點定位算法及自組織過程研究[J]. 傳感技術(shù)學報, 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] 田志輝，金志剛，王 穎. 基于可變長時隙機制的水下傳感器網(wǎng)絡MAC協(xié)議[J]. 計算機應用，2014， 34(7):1947-1950.

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

[13] 洪 璐，洪 鋒，李正寶. CT-TDMA: 水下傳感器網(wǎng)絡搞笑TDMA協(xié)議[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-)，男，廣東汕頭人，碩士，工程師，研究方向：水下傳感器網(wǎng)絡，數(shù)據(jù)收集。

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

TP 391

A

1006-7167(2016)02-0089-05