基于簇的無線傳感網絡流量負載的時隙調度協議
2009-01-01 00:00:00劉明劉銳黃小燕周自波
計算機應用研究 2009年5期
（華中師范大學 a.計算機科學系；b.網絡教育學院 武漢 430079 ）
摘 要：針對大規模的無線傳感器網絡MAC協議在能量有效、低延時等方面的不足，提出一種基于簇的自適應時隙調度協議（ATSP）。整個網絡由一些較小單位的簇組成，在每個簇內構造一棵數據聚集樹，根據數據聚集樹對節點每輪需要發送的數據流量進行加權，決定該節點的時隙大小；然后由簇頭動態調節簇內節點時隙更新頻率和順序，可以降低時隙劃分的能量和時間代價，減少節點的空閑偵聽時間，避免串音。仿真表明，該協議有效地提高了網絡能量有效性，延長了網絡生存周期，降低數據包的延時。
關鍵詞：介質訪問控制協議；時隙；數據加權；數據聚集樹
中圖分類號：TP393文獻標志碼：A
文章編號：1001-3695(2009)05-1855-03
Traffic load aware timeslot scheduling protocolbased on clustering for wireless sensor networks
LIU Minga，LIU Ruia，HUANG Xiaoyana，ZHOU Zibob
(a.Dept. of Computer Science b.School of Network Education Central China Normal University Wuhan 430079 China)
Abstract:Taking account of the drawbacks in energy efficient and lowlatency of the most of largescale wireless sensor MAC protocols，the paper presented ATSP based on clustering.ATSP divided the entire network into some clusters the protocol constructed a data gathering tree in each cluster. Each round the cluster head adjusted the timeslot of nodes according to their weighted traffic load in a proper order and frequency，reduced thus the idle listening and achieved the energy consumption balancing among nodes with a low latency. Simulation results show that the protocol can meet the system requirements in reliability realtime response and energy efficiency.
Key words:MAC protocol; timeslot; data weighting; data gathering tree
大規模的無線傳感器網絡可以潛在運用于軍事、科技以及商業等方面，所以其已逐漸成為當今信息領域新的研究熱點[1]。作為WSN網絡協議棧重要基礎架構的介質訪問控制(medium access control，MAC)協議，決定著無線通道的使用方式，負責為節點分配無線通信資源，直接影響網絡整體性能，成為WSN網絡協議研究的重中之重。無線傳感器網絡中由于節點能量不能補充，如何節省能量成為所有協議研究的重點；同時無線傳感器網絡還要兼顧節點的實時性，這樣對設計有效的MAC協議提出新的挑戰。根據接入信道的策略，在WSN研究中所提出的MAC協議主要分為以下兩種類型：a）基于競爭算法。一般采用沖突避免機制和隨機重傳，在網絡負載較輕時比較有效；但隨著負載增加沖突增多，吞吐量可能降低至零，使得網絡不穩定。b）基于調度算法。把信道劃分為時隙，通過清晰的信道分配帶來更好的信道利用率和處理優先級及不同業務類型的能力。基于調度的MAC協議可以使節點通過消除沖突，避免空閑監聽以及在非活動狀態時關閉節點等方式節省能量，其逐漸成為MAC協議研究的熱點。但是它也面臨一些問題：如何為鄰居節點分配時隙，在多跳網絡環境中，由于網絡環境比較復雜，節點需要傳輸數據量差異較大，如果為每個節點劃分同樣大小的時隙，容易造成某些流量較小的節點的時隙過度浪費；同時現有的MAC協議主要考慮節點的能耗，忽視了節點的延時。
本文提出一種基于簇的自適應時隙調度協議(adaptive timeslot scheduling protocol，ATSP)，根據節點位置信息來構造數據聚集樹動態地預測節點數據流量，對預測的數據流量加權計算節點需要發送數據的期望時隙，以此分配時隙的大小和順序。算法可以避免空閑監聽和串音，降低網絡延時。
1 相關研究
CSMA、SMAC[2]、TMAC[3]都是比較有代表性的基于競爭類的MAC協議。SMAC協議采用周期性的睡眠喚醒機制，把時間軸分成固定長度的周期，每個周期由固定的偵聽時間和睡眠時間組成，并采用了虛擬簇的概念，同一個簇內的節點保持相同的時間調度。但SMAC協議幀長度和占空比(duty cycle)固定，幀長度受限于延遲要求和緩存大小，活躍時間主要依賴于消息速率，特別是當網絡負載較小時，空閑偵聽時間仍然過長。 TMAC在SMAC的基礎上，引入適應性占空比來應付負載變化的情況，但是節點在發送之前加入喚醒前導，增加了發送與接收的能量和時延。
BMA[4]、TRAMA[5]都是典型的基于調度的MAC協議：a）BMA協議，運用了分簇組織網絡，簇頭負責收集成員節點狀態信息并發布調度，每個有數據發送的節點只在自己的發送時槽向簇頭節點發送數據，其余時間休眠。但是BMA在各個階段時長固定，無法適應網絡流量變化，降低了信道利用率。b）TRAMA協議，是一種固定分配類MAC協議。根據局部兩跳內的鄰居節點信息，采用分布式選舉機制確定每個時槽的無沖突發送者。但TRAMA時延較長，不適用于對實時性要求較高的應用，對節點存儲空間和計算能力要求高，實現難度大。
2 ATSP設計
2.1 網絡模型
本文設定傳感器網絡的節點位置固定不變，傳感器節點均有固定容量的數據儲存區。對于大規模的無線傳感器網由于整個網絡數量巨大，將整個網絡分簇，每個簇由一部分傳感器節點組成。其中有一個簇首節點，簇首節點能量較大，在簇內所有節點通過多跳或者單跳的方式把數據發送給簇首，再由簇首發送給基站。
每個簇的拓撲用圖G=（V，E）表示。其中：V表示簇內節點數目，包括簇首節點，每個節點都有惟一的ID；EV×V表示與鄰居節點連接的路徑。由于簇首是簇內的數據接收點，在簇內所有成員節點最終都要傳送給簇首，可以根據傳感器節點所處于位置信息，構造一棵數據聚集樹。本文數據聚集樹構造采用文獻[6]提出的方案。其中簇首為root節點，任何成員節點只能通過數據聚集樹先傳輸給雙親節點，由雙親節點向上傳輸最終傳輸到root節點；雙親節點不能向孩子節點傳輸資料，通過構造數據聚集樹，可以方便地預測節點需要發送的數據量，據此構造節點流量期望值來決定所需時隙大小。同時，根據數據聚集樹來決定時隙分配順序，節點只需要監聽自己孩子節點就可以顯著減低空閑監聽時間，還可以避免串音，降低網絡延時。
2.2 ATSP概述
ATSP由若干輪的數據幀組成，每輪數據幀又可以分為準備階段和數據傳輸階段兩個部分。
1）準備階段 主要用來構造數據聚集樹，根據數據聚集樹對節點的數據量進行加權來決定這一輪該節點的期望時隙大小；同時節點交換鄰居信息表，由于ATSP采用了簇結構，在每個簇內由簇頭負責為每個成員節點動態分配時隙，它通過構造的數據聚集樹來對各節點數據流量進行加權，每個成員節點需要根據自己在數據聚集樹所處的位置決定在該輪需要發送的數據量。假如節點是樹的葉子節點就沒有外源數據，只需要發送自己產生的數據，否則節點發送的數據應該包括自己產生的數據和自己的孩子節點的數據。協議根據節點所需要發送的數據量進行加權計算該輪該節點的期望時隙，簇頭根據各節點的期望時隙來動態為節點分配時隙，分配時隙時要求兼顧網絡的實時性，為節點分配時隙大小和順序時應該盡量減少節點空閑監聽的時間，而節點發送的時隙不能相互沖突，最后實現網絡的時間同步。
2）數據傳輸階段 主要就是節點根據前面的時隙分配表進行數據傳輸。每個節點只需要關心自己以及孩子節點時隙，在自己占有的時隙內向雙親節點傳輸數據，如果孩子節點進入發送狀態，節點需要進入接收狀態，別的時隙內節點進入休眠狀態來節省能量，直到下一輪時隙分配開始。在所有時隙完成后節點就進入下一輪數據幀階段，重復此過程。
2.3 時隙大小劃分
若某輪節點Ni的上一輪時隙為ti，發送數據的平均速率為si，則節點發送數據量為si*ti，節點緩沖區數據量為di。則節點這一輪加權數據量計算如式（1）所示。
Fi=ki(Fo+Fc)+pi(di-si*ti)(1)
其中：Fo表示這一輪與上一輪期間時間內產生的數據量；Fc表示這一輪孩子節點傳輸的資料量；di-si*ti表示上一輪時隙內剩余的資料量。Fo如式（2）所示。
Fo=mi(ni=1ti-mi=1ti)+m′ili=1t′i(2)
其中：mi表示上一輪節點Ni數據生成平均的速率；m表示該輪孩子節點個數；m′i表示這一輪孩子節點時隙內該節點生成的平均速率；t′i表示該輪對應孩子節點的時隙；l為該輪孩子節點的數目。記剩余通信負載權值為pi，新產生數據權值為ki(pi#8226;ki≠0)。
假設Ni為葉子節點，那么該葉子節點沒有孩子節點，所以可推出這一輪節點加權數據量：
Fi=pi(di-si*ti)+kimini=1ti(3)
根據式（2）（3）可以推出葉子節點雙親節點的加權數據量。其中：ci為傳輸給雙親節點比率；fi為孩子節點加權數據量。
Fi=kicili=1fi+kimi(ni=1ti-mi=1ti)+kim′ili=1t′i+pi(di-si*ti) (4)
根據節點處于聚集樹的層次結合式（2）~（4）為每個節點求出這一輪需要發送的數據量。數據傳輸時間與數據量成正比，與信道速率成反比，所以節點Ni下輪的期望時隙e(ti)可由其加權通信負載與加權信道容量的比值確定。根據節點所處的位置由式(3)(4)和加權信道容量(ki+pi)si可得e(ti)=Fi/(ki+pi)si，簇頭按照值e(ti)為節點Ni劃分下輪中的時隙長度。
2.4 時隙分配
時隙分配主要就是根據數據聚集樹以及節點的期望時隙來決定各節點時隙順序，用圖1所示的一棵簡單數據聚集樹來說明時隙分配主要解決的問題。其中：節點A為簇首；E、F、G、H、I為葉子節點；B、C、D為中間節點。在為節點分配時隙時必須遵守如下規則：
a)兄弟節點不能同時向雙親節點發送數據，即E→B和F→B的時隙不能重復。
b)孩子節點的時隙應該優先與雙親節點的時隙，即B→A的時隙應該位于E→B和F→B的時隙之后。
c)雖然節點不在同一分支，但它們之間互相干擾（也就是在自己一跳鄰居內），就不應該給這些節點分配可能重復的時隙，如節點F、G位于一跳范圍內，G→C和F→B兩者時隙會互相干擾，就可能造成串音。
d)相反如果它們不在同一分支，且之間不在一跳范圍內，分配重復的時隙就不會支持干擾，可以降低網絡的延時，如節點F、H不位于一跳范圍內，H→D和F→B兩者時隙不會互相干擾，也就不可能造成串音。
時隙分配算法主要對數據聚集樹進行遍歷，遍歷之前對整個樹進行霍夫曼編碼，每個節點得到不同編碼，結合分配時隙的規則可以得到整個節點的時隙表。具體過程如下：
（a)算法初始化，讀取上一輪的時隙調度表和各節點的信息表。
（b）檢查節點需要更新比例，如果num<n/3，就轉（g)。
（c）對整個數據聚集樹進行霍夫曼編碼，記錄霍夫曼編碼。
（d）進入時隙期望e(ti)計算階段，節點按照后序遍歷的規則計算每個節點加權數據量Fi和期望e(ti)，這里需要結合上一輪和本輪一些信息，每個節點均需要維護一個信息表用來記錄這兩輪的時隙以及鄰居節點的信息。
（e）進行該輪的時隙分配，對數據聚集樹進行后序遍歷，結合時隙分配規則完成一個小支分配后，對另外一個小支分配時隙時，首先檢查霍夫曼編碼長度，如果有相同編碼長度的節點且該節點的編碼值比它小，就檢查該節點是否與該節點干擾，按照規則（c)和（d)為節點分配時隙，繼續遍歷完整棵樹。
（f）完成時隙分配，節點進行時間同步，記錄該輪的時隙調度表。
（g）協議結束，返回時隙調度表。
2.5 時隙分配評價機制
如果每輪均對節點重新建立數據聚集樹，為節點計算加權數據量和期望時隙等工作，無疑又可能對整個網絡造成額外的負擔；且一般的傳感器網絡工作連續性強，在兩輪連續時間內差別不太大，沒有必要重新劃定時隙大小和它們的順序，加入評價機制，當傳感器節點性能低于該機制時，就有必要對整個網絡重新分配時隙。
協議可以在數據傳輸階段完成對節點的時隙評價，假設節點Ni在這一輪分配的時隙為ti，而實際傳輸數據的時間為ri，如果在這一輪中時隙有剩余，該節點時隙利用效率就需要分析。如果ri/ti<μ，該節點的更新因子gi=1，μ為可以承受的比值，這里設定μ=0.75；相反，如果ri/ti>μ或時隙ti被完全利用，更新因子gi=0，統計整個簇內需要更新的節點數目num=ni=1gi，當整個網絡需要更新節點數目超過網絡所賦予的臨界值時，即num>n/3時，在下一輪就必須對節點重新更新時隙。
3 仿真與分析
在ATSP仿真實驗中 設定傳感器節點隨機分布在200 m×200 m區域內，傳感器節點數目為100，每個節點的通信范圍是20 m，各節點初始能量為0.5 J，節點間信道容量為C=50 kbps，數據包大小為64 Byte。主要通過延時和生存周期，進行仿真分析，通過與CSMA、SMAC[3]以及TRAMA協議的性能進行了比較。
圖2中，當負載較小時，由于CSMA是單純基于競爭的協議，不需要額外的控制信息，數據傳輸時延最小。SMAC同樣是基于競爭的協議，只不過它需要增加一些同步開銷，平均時延較CSMA協議大一些。ATSP和TRAMA由于采用時隙調度，從而增加了額外的控制信息開銷。隨著網絡負載的增大，CSMA、SMAC協議的數據包沖突增多，平均時延也隨之增大 而ATSP和TRAMA的平均時延因信道利用率提高沒有太大改變，整體延時要優于CSMA、SMAC協議。通信負載為10 packets/s時節點的生存狀況如圖3所示。其中：x軸代表運行輪數；y軸為還處于正常工作狀態的節點數。隨著時間的推移 CSMA/CA中活動節點大量減少，而其他幾種協議中節點生存周期明顯要長。當負載為40 packets/s時，如圖4所示 CSMA的性能相對于10 packets/s時變化不大，而SMAC中節點失效速率明顯加快，TRAMA中節點失效也比ATSP要快。
在正常工作CSMA中節點射頻模塊一直處于偵聽狀態，能量有效性差。SMAC的睡眠機制減少了能量開銷，但隨著負載的增大數據沖突增加，單位數據量的傳輸能耗增高。TRAMA由于采用了調度，能量消耗也不太大。ATSP中活動節點數減少緩慢，說明其能量消耗在不同負載下均處于一個較低的水平，能量有效性高于其他協議。
4 結束語
ATSP通過構造的數據聚集樹來動態預測各節點的數據量，對數據量進行加權簇首以此調節時隙、時隙更新頻率和順序，從而降低無線傳感器網絡MAC協議的能量開銷，延長了網絡壽命;采用ATSP的MAC協議在對網絡環境動態變化的適應性、數據傳輸延遲等性能上均較已有的一些MAC協議有所提高。
參考文獻：
［1］KAHN J M，KATZ R H，PISTER K S J.Next century challenges: mobile networking for Smart Dust[C]//Proc ofthe 5th Annual ACM/IEEE International Conference on Mobile Computing and Networking.New York:ACM Press，1999：271278.
[2]YE H W Y，HEIDEMANN J，ESTRIN D.Medium access control with coordinated adaptive sleeping for wireless sensor networks[J].IEEE/ACM Trans on Networking，2004，12（3）：493506.
[3]DAM T van，LANGENDOEN K.Anadaptive energy efficient MAC protocol for wireless sensor networks[C]//Proc of the 1st ACM Conference on Embedded Networked Sensor Systems. Los Angeles:ACM Press，2003:170180.
[4]LI J，LAZAROU G.Abitmapassisted energyefficient MAC protocol for wireless sensor networks[C]//Proc of the 3rd Int’l Symposium on Information Processing in Sensor Networks (IPSN 2004). Berkeley: IEEE Signal Processing Society 2004:5560.
[5]RAJENDRAN V，OBRACZKA K.GARCIALUNAACEVES J J.Energyefficient collisionfree medium access control for wireless sensor networks[J].Wireless Networks，2006，12(1):6378.
[6]ERGEN S C，VARAIYA P.TDMA scheduling protocols for sensor networks[R].Berkeley:Department of Electrical Engineering and Computer Sciences University of California，2005.
[7]LAZAROU G Y，LI Jing，PICONE J.A clusterbased powerefficient MAC protocol for eventdriven sensing applications[J].Ad hoc Networks，2007，5(7)：10171030.
[8]KULIK J，HEINZELMAN W R，BALAKRISHNAN H.Negotiationbased protocols for disseminating information in wireless sensor networks[J].ACM Wireless Networks，2002，8（23）：169185.
