徐向藝，王啟明

UASN 中改進(jìn)的錨點(diǎn)定位報(bào)文傳輸方案研究

徐向藝，王啟明

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

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

0 引言

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

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

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

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

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

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

圖1 兩個(gè)高危沖突錨點(diǎn)的示意圖

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

1.1 無(wú)沖突錨點(diǎn)

條件1：當(dāng)兩個(gè)錨點(diǎn)間的距離大于2R 時(shí)，那么無(wú)論需要等待多少時(shí)間，它們的傳輸報(bào)文均不會(huì)發(fā)生沖突，因?yàn)樗鼈兊膫鬏敺秶鷽]有相交區(qū)域。我們將這兩個(gè)錨點(diǎn)稱為嚴(yán)格距離相關(guān)無(wú)沖突節(jié)點(diǎn)。

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

圖2 當(dāng)時(shí)的無(wú)沖突錨點(diǎn)

可以發(fā)現(xiàn)，陰影區(qū)域被第1個(gè)和第2個(gè)錨點(diǎn)覆蓋且沒有任何沖突。當(dāng)時(shí)本條件成立，否則屬于條件2情況?？梢酝茢啵绻麆t可保證錨點(diǎn)不發(fā)生沖突的最小值為，如公式（1）：

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

圖3時(shí)的無(wú)沖突錨點(diǎn)

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

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

公式（5）中，（1）表示我們無(wú)法在負(fù)數(shù)時(shí)間傳輸報(bào)文，

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

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

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

2 最優(yōu)解

本節(jié)首先討論如何獲得時(shí)隙方法的最優(yōu)解，然后以此為基礎(chǔ)，闡述如何對(duì)該最優(yōu)解進(jìn)行拓展以確定本文問(wèn)題的最優(yōu)解。

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

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

3 本文算法

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

3.1 L-MAC-IS

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

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

End for

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

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

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

End for

4 性能評(píng)估

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

圖4 平均報(bào)文傳輸時(shí)間與錨點(diǎn)數(shù)量的變化情況

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

圖5 平均報(bào)文傳輸時(shí)間與錨點(diǎn)最大傳輸范圍的變化情況

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

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

如圖6所示：

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

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

5 總結(jié)

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

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

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

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

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

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

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

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