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

徐向藝，王啟明

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

徐向藝，王啟明

定位問題是水下聲學傳感器網絡的一個關鍵問題，如果節點采集到的數據沒有附上時間和測量位置便沒有意義。針對現有定位算法在報文傳輸效率方面的不足，文中提出了一種改進的定位報文傳輸方案。首先，已知錨點的相對位置及其最大傳輸范圍后，分析了定位時的無沖突報文傳輸條件，然后，定義了定位任務時間最小化問題，并證明該問題可以獲得最優解。在此基礎上，提出了兩種基于調度的低復雜度求解算法。最后，通過多次仿真驗證了所提出的算法的準最優性能及相對其他當前算法的優越性。

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

0 引言

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

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

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

1 網絡模型

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

為了避免任何潛在的報文沖突，我們必須解決的一個問題是使最大等待時間最小化。如果一個傳感器節點有兩個甚至更多個傳輸報文互相重疊，則我們認為發生沖突。但是，因為傳感器節點可能位于媒介中的任何位置，所以，來自錨點的傳輸報文可能在兩個錨點傳輸范圍的相交區域任一位置發生沖突。此時，即使兩個錨點沒有位于聲學傳輸范圍內，它們也有可能在網絡中發生沖突，如圖1所示：

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

為了避免沖突問題，我們引入無沖突錨點概念。簡單地講，如果兩個錨點的距離小于最大傳輸范圍的兩倍，則稱這兩個錨點為沖突高發相鄰錨點，發生沖突的概率較大。在下一小節，我們將證明如何改變等待時間以避免發生錨點沖突問題。

1.1 無沖突錨點

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

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

圖2 當時的無沖突錨點

可以發現，陰影區域被第1個和第2個錨點覆蓋且沒有任何沖突。當時本條件成立，否則屬于條件2情況。可以推斷，如果則可保證錨點不發生沖突的最小值為，如公式（1）：

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

圖3時的無沖突錨點

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

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

公式（5）中，（1）表示我們無法在負數時間傳輸報文，

（2）表示條件1-4的融合。

我們從條件3和4中可以發現，為了保證無沖突報文傳輸，設置一個錨點的等待時間后將會對相鄰無沖突錨點的等待時間帶來約束。這些約束不僅與錨點報文傳輸之后的時間有關，還與錨點報文傳輸之前的時間有關。這一點對于確定公式（5）的最優解非常重要。在下一小節，我們給出如何利用時分多址（TDMA）系統定義公式（5）中的問題。

1.2 TDMA系統下的問題定義

2 最優解

本節首先討論如何獲得時隙方法的最優解，然后以此為基礎，闡述如何對該最優解進行拓展以確定本文問題的最優解。

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

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

3 本文算法

最優解的復雜度（不使用啟發式策略）為N!，當錨點數量較大時可行性很低。在本節中，我們提出復雜度分別為的兩種啟發式算法，可用于不同場景。

3.1 L-MAC-IS

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

算法1：L-MAC-IS :從第I 個錨點開始將所有等待時間設置為0：對

End for

3.2 最優啟動器算法

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

算法2：L-MAC-BS :從最優錨點開始

End for

4 性能評估

本節評估本文算法的性能，并與最優解做比較。為了驗證本文算法的優越性，我們還將其與OCSMA等當前水下MAC協議及傳統的時隙方法做比較。在OCSMA中不允許報文并發傳輸，只有前一錨點傳輸完畢后，后一錨點才能傳輸。可以推測，如果每個錨點在所有其他錨點的聲學傳輸范圍內，則最優OCSMA協議便是定位時間最小化問題的最優解。尋找OCSMA的最優解是個NP難題[12]。因此，我們針對該算法再次使用首個最優啟動器概念，并將其性能與本文算法做比較。每個點的計算，均是103次獨立蒙特卡洛運行結果的均值，如圖4所示：

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

此外，定位報文的長度為50 ms，（使用聲學調制解調器且數據率為1kbps時有50位），足以傳輸錨點ID、位置和傳輸時間等信息。

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

L-MAC-BS、L-MAC-1S（首先選擇序號為1的錨點）和最優解的性能非常接近；如果應用場合對復雜度要求較高，則可選擇L-MAC-1S。由于比較費時，所以對其余仿真結果我們沒有計算最優解的性能。

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

如圖6所示：

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

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

5 總結

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

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

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

[3] Han G, Jiang J, Shu L, et al. 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].系統仿真學報,2013,12 (19): 6174-6177.

[6] 梁玥,劉忠,夏清濤.水下聲學傳感器網絡節點定位算法及自組織過程研究[J].傳感技術學報,2014,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]. Proceedings of the Sixth ACM International Workshop on Underwater Networks. ACM, 2014: 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, et al. 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] Ergen S C, Varaiya P. TDMA scheduling algorithms for wireless sensor networks [J]. Wireless Networks, 2014, 16(4): 985-997.

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

TP393

A

2015.01.20）

1007-757X(2015)07-0014-05

國家自然科學基金（NU1204611）；河南省自然科學基金（132300410278）

徐向藝（1979-），女（漢族），河南平頂山人，平頂山學院，軟件學院，講師，碩士，研究方向：智能算法、網絡安全，平頂山，467002

王啟明（1980-），男，河南魯山人，平頂山學院，軟件學院，講師，碩士，研究方向：軟件工程、物聯網，平頂山，467002