基于MACAW的分簇輪轉調度式水聲傳感網MAC協議*
2017-09-04 00:31:10鮑萬松劉廣鐘
網絡安全與數據管理 2017年16期
鮑萬松，劉廣鐘
(上海海事大學 信息工程學院，上海 201306)
基于MACAW的分簇輪轉調度式水聲傳感網MAC協議*
鮑萬松，劉廣鐘
(上海海事大學 信息工程學院，上海 201306)
針對當前水聲傳感器網絡長時延和低信道利用率的特點，改進傳統的水聲通信網MAC協議MACAW協議，設計出一種新型的分簇輪轉調度式MAC協議CRD-MACAW協議。該協議通過網絡初始化和網絡動態更新對部署在網絡中的傳感器節點按照一定機制進行分簇，網絡中的數據傳輸則分為簇內傳輸和簇間傳輸。簇內傳輸采用分簇時網絡管理節點所分配的輪轉順序進行，節點與節點之間無需發送RTS幀和CTS幀；簇間傳輸則是通過各個簇首節點之間采用MACAW協議來進行的，最終網絡數據匯聚到網絡管理節點供分析使用。仿真結果表明，該協議與傳統的MACAW協議相比，在網絡節點增多、節點整體分布較為分散時，能夠有效降低傳輸時延，提高信道利用率。
水聲傳感網；MAC協議；分簇；輪轉調度；CRD-MACAW協議；MACAW協議
0 引言
近年來，隨著海洋探索的不斷發展，水聲傳感器網絡的研究成為熱點和前沿[1-2]。水聲傳感器網絡是部署在水下環境當中的無線傳感器網絡[3]。由于水下通信環境極其復雜，與陸上無線電通信相比，水聲通信存在著傳輸帶寬有限、誤碼率高、傳輸時延長、信道利用率低、噪聲等多種問題，這些問題對水聲傳感器網絡傳輸協議的設計和實現構成挑戰。
在水下通信中，水聲通信是唯一可行的技術[4]。聲波的傳輸速率約為1 500 m/s，比陸上無線電波傳輸速率低五個數量級。加上復雜的水下通信環境，現階段基于競爭的MAC協議有較好的研究前景。本文在基于競爭的MAC協議MACAW協議基礎上提出了一種分簇輪轉調度式水聲傳感器網絡MAC協議：CRD-MACAW(Clustering Rotation Dispatching MACAW)協議。該協議很好地解決了在復雜水聲通信環境中傳感器網絡規模較大并且節點分布局部集中、整體分散情況下的長傳輸時延問題，能夠更好地適用于海底勘探、海洋環境監測、海洋生物種群分布、海底導航等領域。
1 相關工作
在研究CRD-MACAW協議之前，首先分析目前性能較優的水聲傳感網MAC協議，主要是基于競爭的MAC協議，有文獻[5]和文獻[6]中提到的ALOHA協議以及文獻[7]提到的CSMA協議。由于上述協議是基礎協議，這里不做過多介紹。主要介紹以下兩種協議：MACA協議和MACAW協議。
MACA協議是一種基于握手機制的水聲傳感網MAC協議[8-9]。當發送節點有數據發送時，不是立即發送數據，而是先發送RTS包作為握手信號給接收節點，接收節點收到RTS包時給發送節點返回一個CTS包，發送節點收到CTS包時才開始發送DATA包。MACA協議一定程度上減少了數據包的沖突，提高了信道利用率。但是繁瑣的控制包傳輸消耗了大量的時間，增加了網絡時延，并且數據傳輸完畢時，該協議沒有設置確認機制，也影響了數據傳輸準確率。
圖1 MACAW協議傳輸流程
MACAW(MACA-Wireless)協議[10]是在MACA協議基礎上提出的改良協議。它在MACA協議的基礎上通過增加ACK包實現了數據幀確認功能，提高了網絡傳輸可靠性和吞吐量，圖1給出了MACAW協議的傳輸流程。但是，當水下傳感器網絡規模變大、節點增多并且節點分布不均勻時，大量的RTS、CTS和ACK包將會消耗更多的傳輸時延，從而增加了網絡傳輸整體時延。本文所提出的CRD-MACAW協議在MACAW協議的基礎上進行了改進，以更好地解決上述問題。
2 CRD-MACAW協議設計
CRD-MACAW協議的基本思想是：將分布在水下傳感器網絡中的節點按照特定機制進行分簇，數據傳輸隨之分為簇內傳輸和簇間傳輸。簇內傳輸采用輪轉調度機制，簇間傳輸采用MACAW協議。
2.1 網絡初始化與分簇
首先，在網絡初始化之前預先設定一個網絡管理節點。網絡管理節點擁有三方面功能，第一是對網絡采取一定機制進行分簇；第二是作為整個網絡的數據匯聚節點；第三是負責網絡動態更新。
網絡初始化時，網絡中各個節點廣播自己的發送時間和節點標識。管理節點根據各個節點的發送時間與廣播信息的接收時間來計算管理節點與網絡中各個節點的距離l，并根據l和信號到達的角度α來對網絡中的節點進行分簇。分簇時l和α的值選取范圍根據網絡部署現狀進行隨機設定。例如間距在
分簇完成后管理節點為每個簇設置一個簇號N，同時結合節點標識為各個節點設置標號。這個標號是由簇號N和l來確定的，并且按照l由小到大依次排列，即N1、N2、N3…Ni。這里將每個簇中標號為N1的節點指定為該簇的簇首節點。簇首節點的功能就是本簇內數據匯聚以及簇間通信。分簇完成后，管理節點把節點標號廣播出去，使網絡中的各個節點都能得知自己的標號、自己所在簇的簇號、簇內成員節點的個數和簇首節點，同時也能夠區分出其他簇中的節點。各個節點都會記錄下自己的標號。圖2和圖3顯示出網絡初始化之前的原始狀態和網絡初始化之后的分簇狀態。
圖2 網絡原始狀態 圖3 網絡初始化之后的分簇狀態
2.2 輪轉調度設計
在上節所述的網絡初始化完成以后，網絡中各個節點被分在各個簇內，而且每個節點都有自己的標號。每個簇中按照標號(Ni、Ni-1、Ni-2…N1)排列的順序，亦即l由大到小的排列就是簇內節點的輪轉傳輸順序，而且是經過優化的數據傳輸順序，網絡中節點收到管理節點廣播信息之后會記錄該輪轉順序。
下面討論輪轉調度設計。
第一，輪轉調度流程。輪轉傳輸在各個簇內進行，一個輪轉順序代表一個傳輸時間。網絡初始化之后只有每個簇內輪轉順序第一的節點處于激活狀態，其他成員節點均處于等待狀態。每個節點只有接收到自己上級節點的觸發指令時，才被激活，開始進行數據傳輸。當簇內一個源節點有數據需要發送并且收到上級節點觸發指令時，直接將封裝有觸發指令的DATA包發送給它的下級節點，同時啟動ACK信號接收定時器。當下級節點成功收到DATA包時被激活，立即返回上級節點一個ACK包用以確認數據包成功接收，同時將自己緩存當中的DATA包傳輸給它的下級節點，以此類推，直到數據成功到達簇首節點。簇首節點會將該數據以MACAW協議傳輸給其他簇首節點或者網絡管理節點。同時，簇內傳輸依然按照輪轉順序進行。如果在ACK接收時間內源節點未收到其下級節點返回的ACK確認包，則采用時間退避算法進行數據重傳。當重傳次數達到重傳閾值時認為該節點死亡或發生錯誤，會有相應的容錯機制來進行處理，下文中將會詳述。這里需要強調的是，每個簇的DATA包中觸發指令片段包含了目的節點標號，當其他簇內節點收到不同簇內節點的數據包時，通過辨別節點標號中的簇號來選擇是否接收。當簇號不同時，直接丟棄該數據，因此不同簇內的節點間無法進行數據傳輸。簇與簇之間只有簇首節點采用握手機制進行數據傳輸。圖4給出了CRD-MACAW協議的傳輸流程。
圖4 CRD-MACAW協議傳輸流程
第二，觸發指令設計。簇內節點進行數據傳輸時，如果一個節點被激活，而該節點緩存區內無數據需要傳輸，那么此時輪轉將會停止，從而造成網絡陷入不必要的局部停滯狀態，這顯然是不合理的。這里，在每個節點的數據幀中加入簡短的觸發指令片段，觸發指令片段中包括較短的觸發片段和下一級節點標號等。當一個節點被激活時，如果該節點無數據傳輸，那么它將自己的觸發指令發送給它的下級節點，當它的下級節點收到該觸發指令時，立即發送自己的數據，并返回ACK信息給該發送節點，從而避免了網絡陷入局部停滯狀態。
第三，容錯機制。如果簇內節點死亡之后，輪轉傳輸即將停止，也會造成局部網絡停滯。解決該問題的思想是：當一個源節點的下級節點死亡時，或者如上面所述該源節點在重傳閾值內沒有收到下級節點的ACK信號時，該源節點會發送一個封裝有觸發指令的信號給簇內其他節點，信號內包括自己的標號和下級節點的標號。簇內其他節點收到該信息時，比對自身標號，并且標號為源節點的下下級節點被激活，開始發送數據。同時，源節點將其下下級節點作為自己新的下級節點，記錄在自己下輪數據傳輸的觸發指令中；如果簇首節點死亡之后，簇首節點的上級節點將發送一個廣播信息給全網絡，告知簇號為N的簇首節點已經死亡。此時，網絡中所有節點接收到該廣播信息后，則認為簇號為N的源簇首節點的上級節點擔任該簇的新簇首節點。至此，容錯過程完畢。
2.3 網絡動態更新
在水下傳感器網絡傳輸過程當中，節點死亡、節點流動、節點被海水腐蝕等情況造成網絡中數據傳輸效率降低或局部停滯。針對此問題，CRD-MACAW協議中的網絡管理節點會定期進行網絡動態更新，更新過程與網絡初始化過程相同。更新后的網絡中管理節點會及時清除死亡節點，并進行時間同步，保障各個簇內輪轉傳輸正常有序進行。
2.4 無誤包重傳時延
前文提到，CRD-MACAW協議由于分簇和輪轉調度機制而省去了繁雜的RTS包和CTS包傳輸從而節省了大量的傳輸時間，提高了網絡吞吐量和信道利用率。本節和2.5節著重介紹無誤包重傳時延和帶誤包重傳時延兩種情況下CRD-MACAW協議和MACAW協議對比。其中使用的參數名和意義如表1所示。
表1 文中使用的參數名和意義
首先，在MACAW協議中，n跳節點的平均傳輸時延為：
(1)
其中，Ds-d是源節點到目的節點的距離，由于每跳數據傳輸都需要RTS包、CTS包、DATA包和ACK包進行一次交換，故總傳輸距離是4Ds-d。
MACAW協議中，n跳節點的總傳輸時延是：
TW=nTeq-W
(2)
在CRD-MACAW協議中分為極端情況和一般情況。極端情況在網絡傳輸中出現的概率非常小，甚至可以忽略不計。在此要分別進行討論。
極端情況：網絡中數據傳輸路徑只經過每個簇的簇首節點，直到網絡管理節點，不在簇內進行傳輸。此時n跳網絡傳輸的總時延與MACAW協議相同：
Te-C=TW
(3)
一般情況：網絡中數據傳輸既經過簇首節點，又經過簇內節點。此時，在n跳網絡中經過的節點總數為n+1個。設經過簇首節點的個數為m+1個，其中包括網絡管理節點；設經過簇內節點的個數為g個。那么易知簇間傳輸的總條數為m跳，簇內傳輸的總跳數為g跳。并且有：
m+g=n
(4)
此時，網絡傳輸的總時延為：
(5)
其中，由于簇內傳輸時每跳數據傳輸只需要DATA包和ACK包共兩次交換，簇間傳輸時與MACAW協議相同，需要四次交換，故源節點到目的節點傳輸總距離為(2g+4m)/n倍的Ds-d。從式(5)可知，當g=0時，也就是當網絡傳輸遇到上述極端情況時，兩種協議的網絡傳輸總時延相同。
2.5 帶誤包重傳時延
本節介紹帶誤包重傳情況下的兩種協議網絡時延。需要聲明的是，CRD-MACAW協議和MACAW協議在數據包需要重傳時，均采用二進制指數回退機制。CRD-MACAW協議中分為簇內數據包重傳和簇間數據包重傳兩種情況。設第一次回退時間為t，回退次數為x；設兩個簇內節點間的距離為L1，兩個簇間節點間距離為L2。則CRD-MACAW協議中簇內傳輸時重傳增加時延為：
(6)
簇間傳輸時重傳增加時延為：
t·(2x-1)+xTother
(7)
那么，在CRD-MACAW協議中，重傳增加的總時延為：
(8)
在MACAW協議中，設兩個節點間距離為L，那么發生重傳時，重傳增加的時延為：
t·(2x-1)+xTother
(9)
由式(6)～式(9)可知，當傳感器網絡不中節點增多、節點分布較為分散時，CRD-MACAW協議由于其加入分簇和輪轉調度機制，省去了大量RTS包和CTS包的傳輸，在理論上比MACAW協議要節省重傳時延。
下面討論帶誤包重傳情況下的網絡總時延。在水下傳感器網絡中，造成誤包的主要原因是沖突和誤碼率。針對MACAW協議和CRD-MACAW協議而言，造成誤包的絕大部分原因是誤碼率。而且CRD-MACAW協議中簇內傳輸無法產生沖突，故網絡中發生沖突的幾率很小。在此，只討論由誤碼率引起的誤包重傳。結合2.2節可知，CRD-MACAW協議與MACAW協議一樣用ACK信號作為確認信號傳輸給其上級節點，那么兩種協議的誤碼率PE=1-(1-Pe)LACK，因此，在網絡中存在一定誤碼率且具有重傳機制的情況下，MACAW協議的總時延為：
(10)
那么，CRD-MACAW協議的總時延為：
(11)
3 CRD-MACAW協議仿真
本文采用NS-2網絡平臺[11-12]基礎下的Aqua-Sim水聲傳感網絡模擬器[13]作為CRD-MACAW協議的仿真工具。仿真過程中重點對比CRD-MACAW協議與MACAW協議在傳輸時延上的性能。
3.1 仿真條件
本仿真實驗中重要討論傳輸節點間平均間距以及節點數量對傳輸時延的影響。仿真采用的部分參數如下：數據幀長度2 000 bit，RTS包、CTS包和ACK包的長度均為200 bit，數據傳輸速率為20 000 b/s，節點最大重傳次數為5次，誤碼率為10-5。節點間平均間距和節點數量會在仿真中給出，仿真環境為水聲環境。
3.2 仿真結果分析
圖5和圖6分別是傳感器節點平均間距和節點數量對傳輸時延的影響。由圖5可以看出，當節點數量給定為10個時，隨著節點平均間距的增大，CRD-MACAW協議和MACAW協議傳輸時延都在增大，但是CRD-MACAW協議在節點平均間距不斷增大時呈現出傳輸時延增長速率逐漸減緩的趨勢，而MACAW協議傳輸時延的增長速率不斷增大；同時，整個過程CRD-MACAW協議比MACAW協議傳輸時延平均小約26.4%，而且差距越來越大。這是因為，隨著節點間距的增大，采用CRD-MACAW協議時簇內傳輸由于輪轉調度機制而省去了大量的控制幀傳輸，從而節約了時間；相反，采用MACAW協議傳輸時，隨著節點平均間距增大，大量RTS、CTS包需要不斷長距離傳輸，大幅增大了傳輸時延。
由圖6可以看出，當節點平均間距給定在1 500 m，隨著節點數量的增大，CRD-MACAW協議和MACAW協議的傳輸時延都在增長，但是前者增長速率逐漸減緩，后者增長速率持續增大。整個過程CRD-MACAW協議的傳輸時延比MACAW協議傳輸時延平均小約31.2%，而且差距越來越大。這說明，隨著節點數量的增長，采用CRD-MACAW協議傳輸時，落在簇內傳輸的概率較大，簇內傳輸由于輪轉調度機制而節省了大量傳輸時延，采用MACAW協議時則隨著節點數量增多，控制報文的傳輸次數也相應增多，從而提高了傳輸時延。
通過圖5和圖6的對比可知，在水聲傳感器網絡中，當網絡規模變大、節點數量增多、節點分布較分散時，CRD-MACAW協議在傳輸時延上明顯優于MACAW協議。
圖5 節點個數給定，節點間平均間距對傳輸時延的影響
圖6 節點間平均間距給定，節點數量對傳輸時延的影響
4 結論
傳統的水聲傳感網MAC協議MACAW協議在MACA協議的基礎上通過增加了ACK確認機制，在一定程度上提高了數據傳輸效率和傳輸可靠性。本文提出的CRD-MACAW協議在MACAW協議的基礎上通過分簇和輪轉調度的方式使簇內傳輸過程減少了大量RTS包和CTS包，節省了大量傳輸時間；同時保留了ACK確認機制，保持了MACAW協議的優點。仿真結果表明，在傳感器網絡中節點數量增多、節點整體分布較為分散且局部集中的情況下，與MACAW協議相比，CRD-MACAW協議明顯減少了傳輸時延，提高了信道利用率。CRD-MACAW協議更適合應用于海底導航、海洋環境監測和災害預警等水聲通信領域。
本文未來工作應著力于網絡規模較大時分層協議的設計，以不斷優化CRD-MACAW協議來研究上層路由協議，使二者能夠在通信過程中達到較高的契合度，從而加強網絡資源的利用，降低網絡時延，進一步提高信道利用率。
[1] RICE J, CREBER B, FLETCHER C, et al. Evolution of seaweb underwater acoustic networking[C]. Oceans 2000 MTS/IEEE Conference and Exhibition, 2000:2007-2017.
[2] 劉廣鐘, 耿偉. 水聲傳感器網絡分簇路由協議研究[J]. 微型機與應用, 2012, 31(8):44-47.
[3] AKYILDIZ I F, POMPILI D, MELODIA T. Underwater acoustic sensor networks: research challenges[J]. Ad Hoc Networks, 2005, 3(3):257-279.
[4] 劉文靜. 水聲傳感器網絡MAC協議研究[D]. 大連:大連理工大學, 2015.
[5] Xiao Yang, Zhang Yanping, GIBSON J H, et al. Performance analysis of p-persistent aloha for multi-hop underwater acoustic sensor networks[C]. International Conference on Embedded Software and Systems, IEEE, 2009:305-311.
[6] 王毅,高翔,方世良,等.Aloha-LPD:一種用于水聲通信網的MAC協議[J].東南大學學報(自然科學版),2009, 39(1):12-17.
[7] Fang Dong, Li Yu, Huang Haining, et al. A CSMA/CA-based MAC protocol for underwater acoustic networks[C]. International Conference on Wireless Communications Networking and Mobile Computing, IEEE, 2010:1-4.
[8] Zhao Qichao, LAMBERT A, BENSON C R. FS-MACA: a future scheduling MAC protocol in underwater acoustic networks[C]. Proceedings of the International Conference on Underwater Networks & Systems, 2014:1-5.
[9] Guo Xiaoming, FRATER M R, RYAN M J. A propagation-delay-tolerant collision avoidance protocol for underwater acoustic sensor networks[C]. IEEE Oceans OES and MTS, 2007:1-6.
[10] BHARGHAVAN V, DEMERS A, SHENKER S, et al. MACAW: a media access protocol for wireless LAN’s[J]. ACM Sigcomm Computer Communication Review, 2000, 24(4):212-225.
[11] KANTHIMATHI N, DEJEY. Balanced and multi-objective optimized opportunistic routing for underwater sensor networks[J]. Wireless Personal Communications, 2016:1-24.
[12] 石為人, 黃河, 鮮曉東,等. OMNET++與NS2在無線傳感器網絡仿真中的比較研究[J]. 計算機科學, 2008, 35(10):53-57.
[13] Liu Tongqing, Han Guangjie, Zhu Chuan, et al. Application research on aqua-sim for underwater acoustic sensor networks[J]. Advanced Materials Research, 2012, 605-607:1046-1049.
Clustering rotation dispatching MAC protocol for underwater acoustic sensor network based on MACAW
Bao Wansong, Liu Guangzhong
(College of Information Engineering, Shanghai Maritime University, Shanghai 201306, China)
Aiming at the long delay but low utilization rate of channels of the present underwater acoustic sensor network, traditional underwater acoustic communication network MAC protocol MACAW has been improved into a new clustering rotation dispatching MAC protocol, CRD-MACAW. This protocol rotates the sensor nodes in the network with certain mechanism through the network initialization and network dynamic updating. And the data transmissions in the network are divided into transmissions in cluster and transmissions between clusters. Transmissions in cluster are done according to the rotating order matched by the managing node in network when clustering. RTS frame and CTS frame need not be sent between nodes, while transmissions between clusters are done using the MACAW protocol between the first nodes of every cluster, and finally the data in the network will be gathered at the managing node in network to be analyzed. The simulated result shows that this protocol can decrease the transmission delay effectively and improve the utilization rate of channels if nodes in the network are increasing and the node distribution is decentralized totally when comparing with the traditional MACAW protocol.
underwater acoustic sensor network; MAC protocol; clustering; rotation dispatching; CRD-MACAW protocol; MACAW protocol
國家自然科學基金(61202370)；上海市教委科研創新項目(12ZZ151)
TN929.3
A
10.19358/j.issn.1674- 7720.2017.16.021
鮑萬松，劉廣鐘.基于MACAW的分簇輪轉調度式水聲傳感網MAC協議[J].微型機與應用，2017,36(16)：73-77.
2017-02-22)
鮑萬松(1990-)，男，碩士研究生，主要研究方向：分布式計算與傳感器網絡。
劉廣鐘(1962-)，男，博士，教授，主要研究方向：分布式數據庫、分布式人工智能、計算機網絡技術、網絡計算、CIMS技術、物流信息化技術等。
