基于水聲傳感網絡的樹形拓撲混合MAC協議*

類延增，劉廣鐘，徐 明（上海海事大學　信息工程學院，上海 201306）

基于水聲傳感網絡的樹形拓撲混合MAC協議*

類延增，劉廣鐘，徐 明
（上海海事大學信息工程學院，上海 201306）

鑒于水下傳感網絡的長時延、低帶寬的特點，設計有效的水下無線網絡的通信傳輸協議很有必要。提出一種樹形拓撲結構的結合基于競爭和基于分配兩種模式的混合策略，減少了水聲通信中的握手次數，即減少了RTS/CTS請求的發送次數，利用組播、LRU預留時間策略提高了傳輸效率，整合了網絡通信中ACK包和數據包的發送，既能使所有節點間實現自由通信，又能提高網絡吞吐量、節約能耗。

水聲傳感網絡；組播；加密；延長階段；保留時間

0　引言

如今“智慧城市”、“智慧港口”、“智慧家居”等概念不斷提出并完善，其中無線通信技術作為一條核心紐帶聯通了客戶與無線設備，陸地無線通信技術的成熟，帶動了水下無線傳感技術的發展。無線傳感技術在海洋環境檢測、海底礦物探測、海洋水下搜尋、海洋數據采集、水下機器人作業任務中都起到重要的作用。

水聲通信是目前水下傳感技術的主要方式，存在傳播時延長、帶寬有限這兩個主要不足，除此之外，流動性、水流速度、水的混濁程度等都對通信能力造成影響，使得水聲傳感網絡的吞吐量變低、誤碼率變高、通信質量下降。水聲通信協議的研究旨在通過協議避免沖突的發生，提高通信效率，節約通信能量。水聲通信協議與陸地無線傳感網絡一樣，主要分為基于競爭和基于分配的兩大類。

［1］是基于樹形拓撲結構實現的，該協議引入了馬爾可夫決策過程，使每個子節點通過馬爾可夫決策過程決定下一次傳輸需要的傳送時長，發出請求，父節點結合自身時間片和子節點請求安排合理的傳送時間和時長，子節點分配進行數據的傳送，均衡節點的負載，使網絡達到平衡。ROSS［2］也是一個在樹形分層拓撲中設計的協議，通過引入睡眠模式實現節能，利用自上而下的時間片決策確定各個節點的傳送時間片，時間片決策達到平衡后，每個周期按照平衡時的狀態循環工作。ROSS協議的實現簡便易懂，缺點是協議的環境是完全靜態的網絡，無法動態地調整網絡狀態，在ROSS協議中，也沒有采用ACK應答機制。但此協議減少了握手次數，實現了節能效果。這兩個協議作為樹形網絡的典型代表，都只是實現了單向傳輸，無法實現簇內節點的通信。

S-FAMA［3］、ST-MAC［4］、ESC［5］、R-MAC［6］等協議也都在水聲通信環境中實現了優秀的效果，其中S-FAMA著力解決了隱藏終端的問題，通過對RTS/CTS設置保留時間，達到避免隱藏終端沖突的問題。這些協議大都允許網絡節點的自由通信，頻繁的握手使得需要在耗能方面做出妥協。

1　相關分析

在樹形拓撲中，要實現一個簇集的簇內通信，經過對比設計，在拓撲結構中增加一個簇首節點，稱這個節點為內簇首節點，原來的簇首稱作外簇首節點，分別利用不同的簇首進行簇內和簇外通信，拓撲結構如圖1所示。

圖1　改造后的簇結構

協議Ordered-CSMA［7］中提出，無線傳感信號是同心圓狀的發射波，一個節點在向其中遠端節點發送完信息后，不需要等待其接收完畢，即可向近端節點發出信號。如圖2所示，AB的距離小于AC的距離，A節點可以先向C節點發送數據，A節點發送完后，不需要等待C節點接收完數據信息，可以緊接著向B節點發送數據，兩部分數據可以同時到達目的節點而不發生沖突，比傳統收到確認信息后再次發出要節省時間。

圖2　無線信號傳播示意圖

利用這個特征，在子節點發出外部通信數據后，緊跟著發送內部通信的數據，內簇首負責接收內部通信的數據，而外簇首負責接收需要發送到簇外和匯聚節點的信息，同理，內外簇首任何一個可以先發送信息，當另一個探測到信息發送完后可以緊接著發出自己的信息。內節點需要協調多個簇內節點間的信息，假設每個子節點的信息單獨傳送，需要多次握手協商、傳送，這里采用組播方式，所有簇內子節點接收同一個信息包，每個子節點根據自己的信息分別留取和分析屬于自己的數據段，但是存在多個子節點給同一個兄弟節點發送信息的情況，內簇首需要對接收到的信息進行整合，把目的地址相同的數據整合在同一數據段發送。考慮到信息安全問題，后面需要論述加密機制。

在水下環境中，通信節點具有時空流動性，節點與簇首節點間的距離容易出現變動，就使得節點與簇首節點間的距離存在不確定性。針對這個問題，讓兩個簇首節點位置上無限靠近，在時間上采取相鄰發送，取極限狀態，采用同一個簇首來完成內外信息的交互，如圖3所示即是最終采用的簇結構。

圖3　樹形拓撲的一個簇集

2　協議設計

根據ROSS和Z-MAC［8］的沖突避免機制，如圖4所示，本協議在 RTS/CTS初始化階段，簡單地采用自上而下的交叉的TDMA有序分配，為每個節點分配發送RTS請求的時間片，分配完成后，在以后每個發送周期中都固定不變。每個節點需要發送數據時，在向簇首節點發送RTS包申請時間片時，只能在其分配好的RTS申請時間點發送RTS包。簇首節點根據具體的子節點請求和節點間的距離，合理分配數據傳輸的時間片。

圖4　簇集通信初始化示意圖

考慮到信息傳輸的安全性，在網絡拓撲結構初始化時，每個子節點都需要把自己的公有密鑰發送給簇首節點，簇首節點和子節點之間建立非對稱加密算法，目的是在內部通信階段，簇首節點針對不同子節點的信息，利用其公鑰進行加密，每個收到信息的子節點通過自己的私鑰對信息進行解密，避免了節點惡意獲取其他節點信息。

數據包的格式如圖5所示。在這種數據包格式下，在包頭標記中，需要表明每個節點的順序，而且包含了每個節點的數據長度，方便獲取屬于自己的數據段。其中，每個子節點信息經過整理，包含了多個發送方的數據和標記信息等。其中，Distart表示屬于第 i個節點的數據的物理起始位置，Ltag是包頭標記信息的長度，Lj、Li表示第j個和第 i個節點的數據長度，相應的 Diend表示第 i節點數據的結束位置。

圖5　簇首數據包格式

本協議只為發送RTS請求的節點分配數據發送時間片，其他時間處于睡眠狀態。為了實現這個目標的同時減少握手的能耗，采用預留時間片機制。與協議SFAMA［3］和CSMA/CA中預留時間的概念不同，本協議采用的預留時間片策略，將橫向擴展改為縱向擴展，即預留的時間不是在本次的傳輸時長上延長，而是在次數上進行預留。在這個時間周期內，如果子節點B向簇首節點發送請求并得到了許可，在接下來的n個時間周期中，默認節點B不需要再次發送請求就可以直接進行傳輸，稱B節點處于延長階段。只是簇首節點還要在RTS/ CTS階段進入監聽狀態，而子節點在未收到時間片終結信號的情況下，可以處于睡眠狀態。

有新的節點發出傳輸請求時，采用內存管理中用到的經典算法——LRU算法。LRU（Least Recently Used），最近最久未使用算法，在內存分配時，因為內存空間有限，一些資源不方便一次性全部調入內存中，LRU算法把內存中距離現在最長時間未使用的資源空間替換為接下來需要用到的新的資源，以剔除掉最沒有可能傳輸數據的節點。

具體優先級別規定如下：

Pidle〉Pextend〉Pfirst（3）其中，Pidle是空閑階段優先級，Pextend是延長階段的優先級，Pfirst表示首次正常傳輸的優先級。當對比的優先級相同時，需要看節點申請連接的順序，最早申請連接的節點具有最高優先級，最容易被替換。

實現算法的偽代碼如下：

如圖6，B點發送了新的數據連接請求，簇首節點A在檢索自己的接收時間后，發現沒有合適的空閑時間分配給B節點，D節點正處于延長階段，而D節點在本周期沒有發送數據，簇首節點只能處于空等狀態。A節點檢索對比后發現，可以把D節點的時間段經過調整分配給B節點傳送數據。A節點在接下來進行組播，要在給D節點的數據包中說明下個階段開始斷開其連接，而在給B節點的數據中，說明給B節點協調的傳送時間。

圖6　一個典型的時間階段

總結本協議的特點，首先協議基于樹形分層拓撲結構使得網絡中節點的信息交換分區域聚合，在小區域內達到較高的通信效率，對LEACH協議和ROSS協議經過改進后，實現了網絡中各節點相互通信的要求；利用簇首和子節點把簇內通信信息和簇外通信信息進行整合，簇首的加密組播模式避免了信號沖突、重復多次握手的耗能浪費；傳輸階段舍棄了ROSS中完全靜態的任務循環重復模式，采用預留時間片模式，在盡量減少握手的情況下，保持網絡中節點的高效通信。協議中用到了LRU算法，定義協議名稱為LRU-MAC。

3　模擬對比

在MATLAB中用實驗驗證協議的效果，對比RMAC和ROSS的模擬環境，將一個數據包仿真的接收消耗、發送消耗和睡眠消耗分別設定為13 mW、24 mW和15 μW，傳輸一個數據幀的速率為1 000 kb/s，水聲傳播速度為 1 500 m/s。RTS包包含請求地址、位置信息等，大小為 100 bit，數據幀大小為 2 000 bit，每個周期為200 ms。

通過實驗模擬，首先確定LRU算法中n的合適數值。經對比，網絡平均耗能和網絡吞吐量方面的性能會隨著n值的增大而提高，這是因為n值變大，協議中平均的RTS請求變少，平均握手次數減少，使得耗能和吞吐量開始變優。但當n值過大時會造成LRU算法頻繁置換，耗能和吞吐量方面的性能反而會下降，如圖7、圖8所示，可以看到在模擬環境中，當n取值為4時，吞吐量和網絡耗能處于最佳狀態。

圖7　n取不同值時的平均耗能

圖8　n取不同值時的平均吞吐量

本協議通過模擬實驗，在吞吐量和能耗方面與RMAC和 ROSS兩個協議作了對比。ROSS只是在靜態環境中實現，在能耗上是省去了每個周期發送RTS和ACK包的能耗，但其無法實現簇內節點的通信，在功能全面的協議中，本協議在平均吞吐量和能耗上有明顯的改進。具體對比如圖9、圖10所示。

圖9　不同協議間的平均耗能

圖9中，R-MAC初始化網絡不需要所有的節點都發送初始化數據包，初始組網耗能相對于ROSS和LRU-MAC較少，而ROSS和LRU-MAC的初始化是相似的，子節點都需要向簇首節點發送信息，耗能都比RMAC高。隨著網絡負載增大，R-MAC需要頻繁地進行握手、避免沖突、探測信道，耗能迅速上升并超過其他兩個協議，而ROSS作為靜態網絡不需要再次握手，能耗相對平穩。LRU-MAC需要偶爾握手，它的耗能雖然比ROSS高，但比可以自由通信的同類協議R-MAC要節約耗能。

本協議結合無線信號同方向依次傳播不會發生碰撞的特性，采用組播、LRU預留時間片策略，在吞吐量和耗能方面進行了優化。LRU-MAC協議減少了每次單獨發送RTS和ACK包的負載，在平均吞吐量方面對比于ROSS、R-MAC協議都有很大的提升，在能耗方面明顯比R-MAC要優秀，雖然ROSS平均能耗較小，但本協議在簇首節點傳輸給子節點的信息中整合了ACK包，減小了數據傳輸的誤碼率。

4　結論

本文提出并設計了一種新的LRU-MAC協議，該協議結合傳統水下無線傳感網絡和典型的樹形分層拓撲網絡各取所長設計而成，在總體上以減少節點間的握手次數、空閑時間休眠為手段，通過實驗對比，證明新的協議在網絡平均吞吐量和平均耗能方面都有改進，表現良好，最重要的一點是，本協議突破了傳統樹形分層拓撲網絡只單向傳輸的特點，同時實現了簇內和簇外傳輸。

但是本協議也存在一些弊端需要克服，比如簇首節點的負載要比普通子節點高很多，容易造成簇首節點比子節點提早完成壽命，這個問題在參考文獻［9］中提出了一種解決方法，簇首節點的工作機制也較為復雜，這些問題還要進一步解決。

參考文獻

［1］JITHIN J，SAJI A，HOVANNES K，et al.A hybrid MAC protocol with channel-dependent optimized scheduling for clustered underwater acoustic sensor networks［C］.Proceedings of the 8th ACM International Conference on Underwater Networks and Systems，WUWNet 2013，DOI：10.1145/ 2532378.2532382.

［2］Hong Lu，Hong Feng，Yang Bozhen，et al.ROSS：Receiver oriented sleep scheduling for underwater sensor networks ［C］.Proceedings of the 8th ACM International Conference on UnderwaterNetworksand Systems， WUWNet2013，DOI：10.1145/2532378.2532396.

［3］MOLINS M，STOJANOVIC M.Slotted FAMA：A MAC protocol for underwater acoustic networks［C］.16th IEEE International Symposium on the Applications of Ferroelectrics，ISAF，2006，DOI：10.1109/OCEANSAP.2006.4393832.

［4］HSU C C，LAI K F，CHOU C F，et al.ST-MAC：spatial-temporal MAC scheduling for underwater sensor networks［C］.Proceedings IEEE INFOCOM，2009：1827-1835.

［5］Hong Lu，Hong Feng，Guo Zhongwen，et al.ECS：effcient communication scheduling for underwater sensor networks［J］.Sensors，2011，11（3）：2920-2938.

［6］Xie Peng，Cui Junhong.R-MAC：an energy-efficient MAC protocol for underwater sensor networks［C］.In the Second International Conference on Wireless Algorithms，Systems and Applications（WASA 2007），2007：187-195.

［7］Chen Yinjun，Wang Haoli.Ordered CSMA：a collision-free MAC protocol for underwater acoustic networks［C］.Oceans Conference Record（IEEE），2007，Oceans 2007 MTS/IEEE Conference，DOI：10.1109/OCEANS.2007.4449386.

［8］RHEE I，WARRIER A， AIA M，et al.Z-MAC：a hybrid MAC forwirelesssensornetworks［J］.IEEE/ACM Transactions on Networking（TON），2008，16（3）：511-524.

［9］劉廣鐘，耿偉.水聲傳感器網絡分簇路由協議研究［J］.微型機與應用，2012，31（8）：44-47.

A hybrid MAC protocol in the tree topology based on the underwater acoustic sensor networks

Lei Yanzeng，Liu Guangzhong，Xu Ming
（Information Engineering College，Shanghai Maritime University，Shanghai 201306，China）

According to the features of long delay and low-bandwidth in the underwater sensor networks，designing an effective underwater wireless communication network transporting protocol is necessary.This paper presents a combined protocol in a tree topology，which mixes competition modes and allocation strategy.The strategy reduces underwater acoustic communication handshakes and the numbers of transmissions of RTS/CTS requests by multicast and LRU reservation.That greatly improves transmission efficiency.By integrating the data packet and the ACK packet，the protocol not only achieves freedom communication between all nodes but also improves network throughput and energy-saving effect.

underwater acoustic sensor networks；multicast；encryption；last longer time；reserved time

TN929.3

A

1674-7720（2015）15-0071-04

類延增，劉廣鐘，徐明.基于水聲傳感網絡的樹形拓撲混合MAC協議［J］.微型機與應用，2015，34（15）：71-74.

2015-03-03）

類延增（1989-），男，碩士研究生，主要研究方向：水下聲傳感網絡。

劉廣鐘（1962-），男，博士，教授，主要研究方向：水下聲傳感器網絡、分布式計算。

徐明（1977-），男，博士，副教授，主要研究方向：水下聲傳感器網絡。

上海市教委創新項目資助（12ZZ151）