并行調度兩級輪詢控制傳感器網絡MAC協議分析

官錚,鄒丹,丁洪偉,錢文華

(1. 云南大學 信息學院，云南 昆明 650091； 2. 云南開放大學 機械與電子工程學院，云南 昆明 650091)

典型的無線傳感器網絡采用分層結構，由簇首節點收集子網中的數據并向上層節點轉發最終傳輸到匯聚點，形成了一顆以匯聚節點為根的數據傳輸樹。在樹結構中作為簇首的節點相對普通數據采集節點具有更高的網絡負載，為了避免由信息傳輸累積造成的擁塞，保障數據傳輸時延，傳輸過程中應為簇首節點分配更多的網絡資源。 近年來，各國學者針對傳感器網絡的QoS保障問題做出了大量研究[1-2]，包括MAC(medium access control)、路由層到傳輸層的優化設計。介質訪問控制協議決定著無線信道的使用方式，負責為節點分配無線通信資源，直接影響網絡整體性能，受到了廣泛的關注，從不同角度改善了網絡的時延性能和時間同步條件[3-6]。然而，考慮網絡流量不平衡環境下節點的區分優先級的控制協議相對較少。基于兩級輪詢控制的MAC協議可實現區分節點優先級的服務[7-9]，但數據傳輸權頻繁地在普通節點和中心節點間切換，使得查詢轉化開銷較大。針對上述問題，本文提出一種兩級輪詢并行調度MAC協議(parallel two-level polling control based MAC protocol, PTLP-MAC)優化算法，利用捎帶技術實現了數據傳輸和查詢轉換的并行處理，從而減少查詢轉換開銷、降低時延；最后通過仿真實驗與已有方法對比證明了協議在時延特性方面的改進。

1 PTLP-MAC協議設計

假設網絡中所有傳感器節點都靜止，Sink節點位于網絡區域中心位置，傳感器節點按照與Sink的距離劃分為層，各層位于單跳范圍內的節點組成簇，簇首為位于相鄰內層一跳可達的節點，負責按照PTLP-MAC協議管理簇內節點，并對來自簇內成員節點的數據進行匯聚和融合。

1.1 接收者驅動的區分優先級并行調度

PTLP-MAC采用異步傳輸。數據的傳遞由接收者發起，負責數據收集的Sink節點(包括各層簇首節點)按預先指定的順序向成員節點發送數據請求，節點收到請求信息后發送數據，這樣可有效地避免沖突，且無需保持采集節點的全局同步，收到成員節點發送的數據包后回復ACK確認。

考慮到分層結構帶來的節點間流量不均，PTLP-MAC從數據流量和節點在網絡結構中的影響度考慮，將具有較高的數據流量和實時性要求的簇首設為中心節點，其余成員節點視為普通節點，通過以下策略能為中心節點和普通節點提供區分優先級服務：

1)調度順序：以1, 2, …,N表示簇內的N個普通節點，H表示中心節點。Sink節點按照1→H→2→…→N→H的順序向簇內節點請求數據，由此，簇首節點可獲得更多的信道使用機會。

2)服務策略：每次收到來自Sink節點的數據請求后，普通節點只允許發送一個數據包，中心節點允許發送在緩沖區中排隊等待的所有數據包(包括發送期間新到達的數據包)。

最后，協議采用捎帶機制，在Sink節點回復的ACK確認包中捎帶數據請求信息，成員節點通過偵聽ACK幀判斷自己是否為數據請求對象，從而實現數據傳輸和請求過程的并行處理，減少數據請求占用的時間來達到降低時延的目的。

1.2 介質訪問控制機制

表1所示為各類節點需要維護的信息。

表1 節點保留參量

如圖1所示，PTLP-MAC在IEEE802.15.4基礎上引入3種信息包類型，數據請求包、數據包和確認包，接收者根據Type字段判斷收到的信息類型。

圖1 PTLP-MAC信息包格式Fig.1 PTLP-MAC packet format

并行調度機制主要通過ACK實現。當匯聚節點收到來自采集節點的數據包后發送ACK進行確認，簇內其他活動節點偵聽該ACK信號，判斷自己是否為下一請求對象。如果ACK中的Dest為普通節點地址，則中心節點判斷自己為下一數據請求對象，立即發送數據；若Dest為中心節點地址，且Dsn字段為0，則普通節點判斷自己為數據請求對象，立即發送數據。

并行調度方式下ACK需要增加Dsn及SNEXT字段用于攜帶請求信息，但相對于非并行調度策略中，Sink節點針對每個節點均需要發送數據請求包，采用并行調度策略從請求時間和流量占用上均有所節約。

各類節點介質訪問控制算法如下所示。

算法1 Sink節點控制算法。

1)向中心節點發送數據請求包。

2)接收數據，當收到最后一個數據后，按輪詢表順序在ACK中捎帶普通節點請求信息；若超時未收到數據，則按輪詢表順序向下一節點發送數據請求包。

3)接收1個數據包，在ACK中捎帶中心節點數據請求信息；若超時未收到數據包，則進行1)。

算法2 中心節點控制算法。

1)數據到達進入活動狀態，偵聽信道；

2)若偵聽到數據請求，則發送數據；若偵聽到ACK，則發送數據；

3)按完全服務策略發送完所有數據后，進入休眠狀態。此后若有新數據到達則進行1)。

算法3普通節點控制算法。

1)數據到達進入活動狀態，偵聽信道。

2)若偵聽到數據請求，則發送1個數據包；若偵聽到ACK，根據Dsn和SNEXT判斷是否傳輸數據，若是則發送1個數據包。

3)若緩沖為空則休眠，此后若有新數據到達則進行1)；若緩沖區不為空則繼續偵聽。

基本的RR調度算法實現一般很簡單，而且具有良好的O(1)時間復雜性和可擴展性，但無法提供時延保證。兩級輪詢機制在RR調度的基礎上通過服務路徑(調度順序)區分中心節點和普通節點，為中心節點提供較高的時延特性保障，算法復雜度為O(N)，相比已有兩級輪詢控制機制，PTLP-MAC增設的捎帶機制并未增加算法復雜度。

1.3 PTLP-MAC實例

圖2 給出了一個PTLP-MAC的實例。假設子網中存在1個匯聚節點和3個采集節點，S表示匯聚節點，0號節點為簇首節點，1號和2號節點為成員節點。圖2所示為子網范圍內完成一輪數據傳輸的過程：

t1：S向0號節點發送數據請求包，0號節點接收后向S發送數據，直至緩存區為空，完成發送后進入休眠狀態，直至下一個數據到達后被喚醒。S收到來自0號節點的數據包后，發送ACK確認。

t2：S向0號節點發送最后一個數據包的ACK，將Dsn字段設為0，向下一節點請求數據。

t3：1號節點偵聽到ACK后確認自己為下一請求節點，向S發送數據。

t4：S向1號節點發送ACK，0號節點因有分組到達已被喚醒，通過偵聽其中Dest字段為普通節點地址，從而判斷自己為下一數據請求對象，開始發送數據。

t5：S向0號節點發送最后一個數據包的ACK，其中將Dsn字段設為0，對下一節點請求信息。

t6：2號節點因處于休眠狀態未響應S請求；S節點等待超時后，向0號中心節點發送數據請求幀。

t7：0號節點處于休眠狀態未響應請求，等待超時后，S向1號節點發出數據請求。

圖2 PTLP-MAC信息包格式Fig.2 PTLP-MAC packet format

2 仿真實驗及數值分析

2.1 PTLP-MAC仿真

為了驗證論文所建數學模型對PTLP-MAC性能分析的正確性和有效性，利用MATLAB 7.0對協議運行情況進行仿真，對各節點平均排隊隊長和數據平均等待時延進行統計。模擬環境設置如下：假設網絡規模從6節點增至81節點，節點均勻分布；采用11 Mbps信道，數據包長度為1 100 Byte，定義1個時隙寬度為20 μs，歸一化后數據采集節點數據的采集率為0.002 (數據包/時隙)，發送一個數據包需5(時隙)，Sink節點完成一次數據請求時間為2(時隙)。

表2所示節點在輪詢時刻其緩沖區中平均等待的數據包數，表3所示為節點中數據包等待發送的平均等待時延。

表2 信息分組平均排隊隊長(數據包)

表3 信息分組平均等待時延(時隙)

將仿真得到的中心節點和普通節點仿真實驗結果對比，比較顯示，當網絡規模和系統負載隨節點數增大時，節點緩沖區中平均等待的數據包數量和數據平均等待時延均有所增加，中心節點中平均等待發送的數據包數量和數據包平均等待時延均明顯小于普通節點，因此PTLP-MAC能為中心節點提供較好的時延保證，有效實現節點優先級區分，避免數據在傳輸匯聚樹中的根節點處發生擁塞。

2.2 輪詢控制MAC協議比較

目前基于調度的MAC協議在調度策略和休眠機制上各有所長，但信道接入方式大多基于Round Robin控制方式；另外，文獻[8]中提出了離散時間兩級輪詢控制策略以實現節點優先級的區分，本文在此基礎上通過發送和請求的并行處理以減小查詢請求開銷，將對PTLP-MAC、文獻[8]及Round Robin (RR)進行比較，主要從時延保障角度出發，針對平均循環查詢周期、發送時刻節點緩沖區的平均排隊隊長和數據發送平均等待時延等進行分析比較，對本文所述控制協議進行性能評估。

2.2.1 平均循環周期

平均循環周期定義為Sink節點按查詢表順序對成員節點完成一輪數據請求耗費的平均時間。圖3為普通節點數從5增加到80，網絡平均循環周期的變化趨勢。

圖3 平均循環周期Fig.3 Mean cycle time

隨著節點數的增加，文獻[8]平均循環周期略大于RR，這是由于文獻[8]通過增加請求次數來保障對中心節點的高優先級服務，但也增加了數據請求開銷，PTLP-MAC通過ACK捎帶節約了數據請求時間，隨著網絡負載加大后捎帶更易實現，因此隨著節點數的增加，PTLP-MAC在平均循環周期上的優勢更加明顯。

2.2.2 平均排隊隊長

平均排隊隊長定義為成員節點在響應數據請求時，其緩沖區內排隊等待發送的平均數據包數量。文獻[8]和PTLP-MAC節點被區分為中心節點和普通節點2類，在此將分別討論。由于RR中沒有對節點類型進行區分，所有節點公平接入，而文獻[8]及PTLP-MAC通過查詢路徑和服務策略的設置將更多的信道接入機會分配給中心節點，因此，如圖4所示，文獻[8]及PTLP-MAC中心節點平均排隊隊長明顯低于RR。將2類兩級輪詢控制方式下的中心節點平均排隊隊長進一步進行比較，如圖5曲線圖所示，PTLP-MAC控制下的平均排隊隊長小于文獻[8]。由于文獻[8]中Sink每次向普通節點發送請求之前都要優先向中心隊列請求數據，相當于增加了相鄰2個普通隊列發送數據的時間間隔，因此如圖6所示在相同網絡環境下，文獻[8]普通節點平均排隊隊長略大于RR。相比之下PTLP-MAC由于將數據發送和請求并行處理，如圖4～6所示，該方法在確保中心節點優先級的同時也對普通節點的服務質量提供保障，2類節點排隊隊長均小于RR。

圖4 中心結點平均排隊隊長比較Fig.4 Comparison of average packets length in key node

圖5 兩級輪詢機制中心節點平均排隊隊長比較 Fig.5 Comparison of average packets length in center node between two-level polling schemes

圖6 普通節點平均排隊隊長Fig.6 Average packets length in normal nodes

2.2.3 平均等待時延

平均等待時延定義為從數據包進入節點到被允許發送的平均時間間隔。圖6～7所示為3類輪詢控制策略下節點中數據的平均等待時延，由于PTLP-MAC在查詢路徑和服務策略上的設置，使中心節點中數據包的平均等待時延遠低于普通節點，另外采用ACK捎帶請求信息，可減小數據請求包的發送數量，尤其在高負載環境下顯著降低了數據請求開銷。圖7是PTLP-MAC與文獻[8]和RR的中心節點平均等待時延的比較，其中PTLP-MAC與文獻[8]的時延明顯低于RR，為進一步對比PTLP-MAC和文獻[8]，將對比圖中相關部分在圖8放大顯示，如圖9所示，PTLP-MAC中心節點的時延特性低于文獻[8]。

圖7 中心結點平均等待時延Fig.7 Average waiting time in center node

圖8 兩級輪詢機制中心節點平均等待時延比較Fig.8 Comparison of average waiting time in center node between two-level polling schemes

圖9 普通節點平均等待時延Fig.9 Average waiting time in normal nodes

3 結束語

本文針對基于調度的無線傳感器網絡輪詢控制MAC協議族在時間同步以及非均衡傳輸等方面的不足，從時延保障的角度出發，提出了一種接收者發起的兩級輪詢控制并行調度MAC協議優化算法。協議根據節點數據流量及在分層結構中的身份(簇首或成員)，將節點劃分為中心節點和普通節點，通過輪詢過程中輪詢路徑以及服務方式的設置為中心節點分配了更多的信道資源，同時采用ACK捎帶技術實現數據發送和請求的并行處理，有效降低數據等待時延，且控制過程中無需進行全局時間同步。此外，本文采用嵌入式馬爾可夫鏈和概率母函數的方法對提出的進行數學建模并實現了平均循環周期、平均排隊隊長和平均等待時延等關鍵參數的精確解析，從理論上證明了該協議在確保時延性能上的有效性。

參考文獻:

[1]文浩,林闖,任豐原,等.無線傳感器網絡的QoS體系結構[J]. 計算機學報, 2009, 32(3): 432-440.

WEN Hao， LIN Chuang， REN Fengyuan， et al. QoS architecture in wireless sensor network[J]. Chinese Journal of Computers, 2009, 32(3): 432-440.

[2]TAN J, SHROFF N B. Transition from heavy to light tails in retransmission durations[C]//IEEE INFOCOM. San Diego, USA, 2010: 1-9.

[3]RAJENDRAN V, OBRACZKA K, GARCIA J J. Energy-efficient, collision-free medium access control for wireless sensor networks[C]//Proceedings of the ACM SenSys. Los Angeles, 2003: 181-192.

[4]SALAJEGHEH M. HyMAC: hybrid TDMA/FDMA medium access control protocol for wireless sensor networks[C]//Proceedings of PIMRC. Athens, Greece, 2007: 1-5.

[5]張德升,李金寶,郭龍江.基于多信道預約的傳感器網絡MAC協議研究[J]. 通信學報, 2011, 32(4): 126-137.

ZHANG Desheng, LI Jinbao, GUO Longjiang. Study on multi-channel reservation based MAC protocol for sensor networks[J]. Journal on Communications, 2011, 32(4): 126-137.

[6]YANG P, ZI L, DAJI Q, et al. Delay-bounded MAC with minimal idle listening for sensor networks[C]//IEEE INFOCOM. Shanghai, China, 2011: 1314-1322.

[7]劉強,張中兆,張乃通. 排隊優先權站點輪詢系統的平均周期時間[J] . 通信學報, 1999, 20 (2): 86-91.

LIU Qiang, ZHANG Zhongzhao, ZHANG Naitong. Mean cyclic time of queueing priority station polling system[J]. Journal of China Institute of Communications, 1999, 20 (2): 86-91.

[8]LIU Q, ZHAO D, ZHOU D. An analytic model for enhancing IEEE 802.11 point coordination function media access control protocol[J]. European Transactions on Telecommunications, 2011, 22: 332-338.

[9]姚道遠, 張寶賢,劉海. 保障監測時延的無線傳感器網絡感知調度算法[J]. 電子與信息學報，2010, 32(7): 1591-1596.

YAO Daoyuan, ZHANG Baoxian, LIU Hai. Algorithms for detection latency guaranteed scheduling in wireless sensor networks[J]. Journal of Electronics and Information Technology, 2010, 32(7): 1591-1596.

[10]凡高娟, 孫力娟, 王汝傳, 等. 非均勻分布下無線傳感器網絡節點調度機制[J]. 通信學報, 2011, 32(3): 10-17.

FAN Gaojuan, SUN Lijuan, WANG Ruchuan, et al. Non-uniform distribution node cheduling scheme in wireless sensor networks [J]. Journal on Communications, 2011, 32(3): 10-17.

[11]IBE O C, XIAN C. Stability conditions for multi-queue systems with cyclic service[J]. IEEE Trans Aut Control, 1988, 33(1): 102-103.

[12]趙東風, 鄭蘇民. 完全服務排隊模型分析[J] . 電子學報, 1994, 22( 5): 102-107.

ZHAO Dongfeng, ZHENG Sumin. Analysis of a polling model with exhaustive service[J]. Acta Electronica Sinica, 1994, 22(5): 102-107.

[13]ZHAO D. Performance analysis of polling systems with limited service[J]. Journal of Electronics, 1998, 15(1): 43-49.