一種基于大規模網絡分解和協調的WSNs MAC協議*

林鐘楷，程良倫

（廣東工業大學自動化學院控制網絡與系統研究所，廣東廣州 510006）

0 引言

目前，大規模無線傳感器網絡（WSNs）的路由協議大多采用了樹狀拓撲結構［1］，通過分簇和Sink節點實現分層管理，以減少網絡控制的復雜程度。針對這種結構，文獻［2］中Lu G等人提出一種基于路徑規劃原則的DMAC協議，根據數據的傳輸路徑來規劃信道，引入交錯的監聽睡眠調度機制，保證數據在多跳路徑上的連續傳輸。文獻［3］中的Barroso A等人提出以簇為規劃核心的混合型協議μ-MAC，該協議以Sink節點為核心，向上與其它Sink節點對信道實行競爭，向下對下層節點進行統計和分配，實現節點的有序接入。而文獻［4］中，古連華等人對文獻［3］做了改進，通過加入下層節點到Sink節點的數據通信預約機制，進一步提高了網絡的自適應性。文獻［5］則進一步對網絡進行劃分，引入了虛擬群的結構，提出了基于虛擬群的信道接入和休眠管理體制，強化了網絡的管理，避免了沖突和時延。

上述協議在一定程度上能夠解決大規模節點分布的網絡中的能量和效率問題，但僅僅參考節點的自身資源，沒有考慮到隨著網絡規模的擴大所帶來的簇的規模擴大化和結構復雜化。當網絡規模過大時容易帶來簇與簇之間的相互牽擾，以及簇內節點過多帶來的劇烈競爭問題。本文提出一種基于大規模網絡分解和協調的自適應MAC協議（an adaptive MAC protocol based on decomposition and coordination of large-scale networks，ABDC-MAC），其主要思想是:按照網絡層次和時間關聯性，使用文獻［6］提出的分解方法對樹狀拓撲結構進行串行和并行劃分，同時引入網絡結構、節點資源、通信時間等因子，采用文獻［7］中提出的RBRS方法對節點參與網絡競爭的概率進行調整。該協議實現了網絡結構的優化，大大減少了復雜網絡結構帶來的能量和通信問題。

1 協議的提出

1.1 網絡結構

假定存在如圖1所示樹狀結構，同質節點隨機分布在正方形區域中，基站（BS）的能量不受限制，節點周期性地遙感所有傳感器的數據，并通過多對一的匯聚模式逐級由子節點向父節點傳輸，并最終匯集到Sink節點，再由Sink節點傳遞到基站。在這種樹狀結構中，只有父子關系的相鄰節點存在業務轉發，但臨近節點的業務時間相關性較強。這種結構的父子節點數據關系與傳統分群協議中成員與群首的業務模式類似。本文在樹狀結構與分群協議［5］的基礎上，對網絡進行進一步的細分，通過降低簇的規模實現網絡的靈活性。

圖1 樹狀拓撲網絡結構Fig 1 Architecture Tree topology network

1.2 ABDC-MAC協議對網絡的分解

本文提出的網絡分解方法分為串行分解和并行分解［6］2種模式，其分解的最終目標是把網絡分解為包含10～20個節點的子項目組，每個項目組有一個現實（通過串行分解）或者虛擬（通過并行分解）的父節點。首先，對網絡使用串行分解，得到第一層的子節點群，然后對數量大于20的子節點群使用串行分解，得到第二層的子節點群，繼續對未達到分解目標的節點群繼續進行分解，直到達成分解目標為止。同時在每一層引入并行分解機制，對每一層的子節點數目進行限制。

1）串行分解

串行分解主要通過查找節點的傳播路徑來實現，按照網絡的樹狀架構，各個節點的信息總是通過多對一的匯聚模式逐步向Sink節點和基站匯合，與匯聚節點相關的節點構成了一個子節點群，而匯聚節點本身則作為該群的父節點存在。串行分解就是k－1層匯聚節點對與其有數據關聯關系的k層節點的劃分，通過對k層節點上傳數據的關聯關系進行鑒別，區分出匯聚節點及其關聯節點，并重新定義匯聚節點為k層節點，與匯聚節點關聯的節點為其子節點k+1層。同時，對除了匯聚節點及其關聯節點之外的獨立節點暫時將其分在k層。串行分解后，會形成以k層匯聚節點為父節點的群和零散的獨立節點。

2）并行分解

串行分解完成后，如果k層同時存在匯聚節點和獨立節點，或者獨立節點的個數超過分解目標，則對獨立節點進行并行分解，其原則如下:

a.使得該集合中的所有節點與其它節點的活動沒有時序關系;

b.若完成a步驟后，該集合中的節點數超過分解目標的，則對該集合進行切割，通過設置時間標志，將集合中的節點按照時間關系分割為2個集合;

c.若完成b步驟后，集合中的節點數仍超過分解目標，則繼續執行b步驟;

d.對于每個集合，隨機選擇一個節點作為虛擬父節點，位于k層，而其余節點為子節點，位于k+1層。

同時，若匯聚節點與虛擬匯聚節點的數量超過分割目標，同樣進行并行分解，其分解原則與獨立節點的分解原則相同，但最后的虛擬父節點由k－1層的相關匯聚節點擔任。

通過上述的串行和并行分解，網絡的結構如圖2所示。由于進行了基于路徑和時間的分解，各個最小群組間的時序關系達到了最小關聯，最大可能性地減小了群間通信的串擾。

圖2 ABDC-MAC協議拓撲結構Fig 2 ABDC-MAC topology

1.3 ABDC-MAC協議的運行

本文提出的ABDC-MAC協議的運行分為兩部分:建立階段和運行階段。在建立階段，主要是對網絡的分割、同步和初始化。而在運行階段，主要是節點自身網絡參數的主動調整與上傳，使得整個網絡參數得到調整，適應網絡流量的動態變化。

1.3.1 建立階段

建立階段主要是分為2步:對大規模網絡進行串行和并行分解，并建立節點的上下層節點信息表和處理節點同步問題，同時采集節點的初始信息。具體步驟如下:

1）網絡分割

在網絡的分割階段:1）由Sink節點做一個長度為一個調度周期的開始信號廣播，Sink節點下屬的子節點收到開始信號后，將持續監聽網絡;2）每一層的匯聚節點使用嵌套點名法對其直屬的子節點進行點名，得到回應后向其傳遞下一層的隸屬節點信息和簡單同步信息。當子節點的點名完成后，向上一級匯聚節點報告。嵌套點名法如圖3所示;3）對于獨立節點的虛擬父節點采取同樣的方法，對于匯聚節點的虛擬父節點，則對其每一個子節點進行點名。

同時，節點上會建立上游信息表（表1）和下游信息表（表2），對上下游的節點進行登記和管理，主要用于休眠時間同步和網絡參數計算。其中，R，T和NS為節點的資源負載參數、時延參數以及網絡復雜度參數。

表1 上游信息表Tab 1 Present node’s info

表2 下游信息表Tab 2 Child node’s info

圖3 使用嵌套點名法對節點進行分割Fig 3 Decomposition the network by roll-call method

2） 休眠時間同步和節點信息初始化

休眠時間的同步和節點信息初始化由該網絡的父節點發起，父節點根據網絡承載業務和時延要求設定休眠占空比，并選擇休眠開始時間進行廣播，其他節點接收后，根據上游信息表確定時候為父節點，若是，則在調度信息中加入，否則，丟棄。調度信息記錄完成后，節點上傳Rs，Ts，NSs和時鐘參數，父節點接收后，反饋時鐘漂移校正參數，并完成本次同步過程。

1.3.2 運行階段

ABDC-MAC協議的運行模式如圖4所示:

1）協議總體上采用競爭型架構，在每一層由父節點（包括虛擬父節點）競爭一定時長的信道使用權，父節點競爭到信道使用權后，將使用權劃分為多個時長，由其子節點競爭。

2）父節點對信道的競爭原則與文獻［8］的原則類似，但引入一個參數P（s）。該參數代表節點在信道競爭階段選擇接入信道的概率。該參數與父節點及其下屬子節點的資源負載R，子節點與父節點的通信時長T和該節點群的網絡復雜程度NS，以及競爭期時隙選擇有關。同時需要指出的是，節點在上傳數據的時候，還需將自己現在的Rs，Ts和NSs參數上傳，作為上級節點的計算參考值。

3）子節點對信道的偵聽采用跟隨監聽方式，即從頂層節點開始跟蹤，若在一個競爭周期內檢測到得到信道使用權的節點不是自己的上級節點的時候，會轉入休眠節點直到下一個周期的到來;若為自己的上級節點，則會逐級跟蹤，直至到達自己的額競爭周期為止。

4）對于底層節點，由于其數目較少（小于預訂分解目標20），故采取輪詢的方法，一次性采集20個節點的數據并在上層父節點整合上傳。

5）若遇到路由協議更換Sink節點的情況，則只對出現變動的分組進行重新分解，以減少由組織網絡帶來的時間和能量損耗。

圖4 ABDC-MAC協議的運行Fig 4 Operation of ABDC-MAC protocal

2 仿真與實驗分析

本文提出的ABDC-MAC協議在NS-2平臺進行仿真，為了對比評價，同時實現了ABDC-MAC和S-MAC協議。測試的性能指標有:ABDC-MAC的組網效率，ABDC-MAC協議與S-MAC協議的節能效率和網絡延時對比。網絡的主要設定參數如表3所示。

表3 仿真參數Tab 3 Network simulation parameter

表4列出了ABDC-MAC協議的組網效率，可以看出:當網絡初始化或者其構造發生較大的變動的時候，ABDCMAC協議需要較長的一段時間進行組網;而當由于路由更換Sink節點等原因發生小范圍的變化時，ABDC-MAC協議可以較快地調整好網絡。

表4 組網效率Tab 4 Networking efficiency

由圖5可以看出:在運行中，由于節點只需偵聽與自己有關的上層節點是否得到網絡，而不必每個時段都進行偵聽，ABDC-MAC協議運行階段的能耗遠遠低于一般競爭型協議。不僅很好地彌補了組網階段的能耗，在總體能耗上也有很大降低。

圖5 節點平均能耗Fig 5 Average power consumption of each node

由圖6分別列出了ABDC-MAC協議對比S-MAC協議的網絡延時。可以看出:雖然增加網絡復雜度帶來了一定的網絡延時，但由于大規模網絡下組網更加合理，帶來的碰撞和重傳次數的減少，節點的延時大致與S-MAC協議相近，在數據量大的情況下甚至優于S-MAC協議。

圖6 節點時延性能實驗Fig 6 Time delay property experiment of nodes

3 結論

本文提出一種基于大規模網絡分解和協調的自適應MAC協議，該協議通過對網絡的二次重構和節點的優先級計算實現大規模網絡的有序化。仿真結果表明:在大規模組網的情況下，該協議總體能耗低、傳達率高，且具有一定的自適應性，同時網絡時延并沒有因為分層而增加。該協議對大規模無線傳感器網絡有良好的適用性。

［1］Krishnamachari B，Estrin D，wicker S.The impact of data aggregation in wireless sensor networks［C］//The 22nd International Conference on Distributed Computing Systems Workshops，Vienna，Austria，2002:575 －578.

［2］Lu G，Krishnamachari B，Raghavendra C S.An adaptive energyefficient and low-latency MAC for data gathering in wireless sensor networks［J］.IEEE IPDPS，2004，224:26 －30.

［3］Barroso A，Roedig U，Sreenan C.μ-MAC:An energy-efficient medium access control for wireless sensor networks［C］//Proc of European Workshop on Wireless Sensor Networks，2005:

［4］古連華，程良倫.A μ-MAC:一種自適應的無線傳感器網絡MAC 協議［J］.自動化學報，2010，1:54－59.

［5］Li J，Lazarou G.A bit-map-assisted energy efficient MAC scheme for wireless sensor networks［C］//The 3rd Int’l Symp on Information Processing in Sensor Networks，IPSN 04，New York，2004:55－60.

［6］程 序，吳 澄.大規模項目調度問題的分解和協調優化方法［J］.清華大學學報:自然科學版，2009，49:40 －43.

［7］Herrolen W，Reyck B D，Demeulemeester E.Resource constrained project scheduling:A survey of recent develop-ments［J］.Computers＆ Operations Research，1998，25（4）:279 －302.

［8］Ye W，Heidemann J，Estrin D.An energy-efficient MAC protocol for wireless sensor networks［C］//Proc 21st Int’l Annual Joint Conf on Computer and Communications Societies，IEEE，New York，2002.