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

徐向藝，王啟明

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

徐向藝，王啟明

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

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

0 引言

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

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

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

1 網(wǎng)絡(luò)模型

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

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

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

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

1.1 無沖突錨點

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

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

圖2 當時的無沖突錨點

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

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

圖3時的無沖突錨點

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

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

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

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

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

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

2 最優(yōu)解

本節(jié)首先討論如何獲得時隙方法的最優(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)度的錨點之后也不會導(dǎo)致沖突的最早時隙。然后，重復(fù)相同步驟，直到最后一個錨點調(diào)度完畢。最后，我們計算使用時隙的數(shù)量，在所有N!個可能序列中，我們選擇時隙數(shù)量最少的序列。

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

3 本文算法

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

3.1 L-MAC-IS

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

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

End for

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

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

算法2：L-MAC-BS :從最優(yōu)錨點開始

End for

4 性能評估

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

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

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

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

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

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

如圖6所示：

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

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

5 總結(jié)

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

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

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

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

[6] 梁玥,劉忠,夏清濤.水下聲學(xué)傳感器網(wǎng)絡(luò)節(jié)點定位算法及自組織過程研究[J].傳感技術(shù)學(xué)報,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

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

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

王啟明（1980-），男，河南魯山人，平頂山學(xué)院，軟件學(xué)院，講師，碩士，研究方向：軟件工程、物聯(lián)網(wǎng)，平頂山，467002