WSN 中滿足公平性的時分復用調度算法

高 強，李英濤，2，孫大洋，張 婧，2

（1.吉林大學 計算機科學與技術學院，吉林 長春130012；2.吉林大學 符號計算與知識工程教育部重點實驗室，吉林 長春130012；3.吉林大學 通信工程學院，吉林 長春130012）

0 引 言

無線傳感器網絡由一系列能量有限的節點組成，如今已被廣泛應用于各種應用環境［1］。在某些應用環境中，如自然環境監測、工業生產監測等，網絡中的各個節點周期性產生數據的速率差異較大［2］。如果每個節點仍然按照相同的概率訪問信道，勢必會造成節點共享信道的不公平性，從而造成網絡延時的增大和網絡能耗過快、降低網絡吞吐量和網絡生存期。因此，考慮公平性的信道調度研究是十分必要的。

無線傳感器網絡中節能和數據傳輸中的沖突避免問題與MAC協議密切相關［3］。MAC 協議主要負責節點接入無線信道，是其它協議實現的基礎，在無線傳感網絡中起著決定性作用［4］。在MAC協議中，根據信道的分配方式，可分為基于TDMA 的時分復用固定式和基于CSMA 的隨機競爭式兩種。基于時分復用的MAC 協議為網絡中的節點分配獨立的時隙，以避免節點間的相互沖突，節點在不屬于自己的傳輸時隙內轉入休眠狀態以減少能量消耗，且能夠在一定程度上保證網絡傳輸的實時性［5］。

本文的設計目的是在深入分析現有的典型TDMA 調度算法的基礎上，改進并提出一種能夠有效滿足信道分配公平性的方法。

1 相關工作

為了滿足信道分配的需求，研究人員已經提出了大量有關TDMA 的算法［6］。

文獻 ［7］中提出了一種結合CSMA 和TDMA 優點的混合MAC協議Z－MAC。Z－MAC協議的主要思想是節點根據網絡信道的競爭程度，自適應地調整信道的接入方式。在低業務的情況下，CSMA 作為接入方式；在高業務的情況下，TDMA 作為接入方式。Z－MAC 是一個分布式的協議，具有良好的可擴展性，但是隨著網絡密度增加會引入較多的控制開銷，且在低業務情況下延時較大。

文獻 ［8］中提出了一種流量自適應介質訪問協議TRAMA，該協議由相鄰節點協議、傳輸時間安排交換協議和自適應選舉算法組成，根據相鄰區域的節點流量信息來選擇當前時隙的發送節點和接收節點。TRAMA 通信開銷小，但是延遲較長，比較適用于周期性數據采集和監測無線傳感器網絡方面的應用。

文獻 ［9］中提出了一種基于圖染色理論的時分復用調度算法GCSA，該算法分為兩個階段：染色階段和調度階段。染色階段借鑒Brélaz染色策略，提出了一種分布式頂點染色算法DVCA，以達到接近最優的獨立集劃分。調度階段根據染色階段得到的染色結果使用基于優先權的調度策略為獨立集分配時隙。該算法具有可擴展性且能得到較少的顏色以最大化獨立集，但是調度策略解決網絡的公平性問題有待改進。

文獻 ［10］中提出了兩種集中式時分復用調度算法：基于節點的調度和基于層次的調度。這兩種算法使用頂點染色方法，以得到最小化無沖突時隙分配為目標，其性能取決于節點的層次分布狀況，能夠得到較少時延，但可擴展性較差。

針對以上協議目前存在的問題，本文基于DVCA［9］圖染色算法，使用考慮通信干擾的沖突模型對非簇頭節點的通信實現無沖突調度。節點間通過跟鄰居節點進行交互獲得局部信息進而做出決策，并且為流經數據量大的節點優先分配時隙。該調度算法有效地解決了數據流量分布不均勻的網絡場景中信道分配的公平性問題，在降低能耗的同時保證網絡具有較高的數據傳輸率。

2 網絡模型

建立一個由n個隨機部署的傳感器節點構成的自組織網絡，其應用場景為周期性的數據采集。將此傳感器網絡抽象成圖G＝ （V，E）結構，圖中點集V 代表網絡中的節點，n＝｜V｜表示網絡中的節點數目，邊集E∈V×V 表示節點間的通信鏈路。若節點i和j 間形成一條路徑，則圖G中有 （i，j）∈E。由于網絡為同構網絡，因此可以在圖G中使用無向邊來表示鏈路，即若 （i，j）∈E，則 （j，i）∈E。

根據網絡特點作出如下假設：

（1）數據匯聚點DS位于一個方形觀測區域A 的內部。所有節點在部署后不再發生位置移動。

（2）使用DWEHC［11］分簇協議得到所需要的網絡拓撲結構。分簇后的網絡結構如圖1所示。

圖1 分簇網絡結構

（3）簇內節點采用多跳模式使用基于時分復用的MAC協議與簇頭節點通信，簇頭節點為簇內節點通信分配CDMA 編碼以避免簇間沖突，而簇頭節點以單跳模式使用基于競爭的MAC協議來向基站節點傳輸數據［12］。

（4）每個節點都是同構的，且有一個唯一的標識（ID）。

（5）網絡中的節點可以自由調整發射功率，支持雙向數據通信［13］。

（6）每個節點通過彼此通信知道自己及其直接鄰居節點的地理位置。

（7）無線傳感器網絡中節點間的傳輸沖突分為主沖突和次沖突。本文使用文獻 ［9］中得到沖突圖的方法定義節點間的沖突關系。

3 算法介紹與相關定義

3.1 DVCA染色算法描述

將大規模無線自組織網絡抽象成圖G＝ （V，E）結構，圖中的點集V 代表網絡中的鏈路，這樣把一個無線網絡抽象為圖，進而節點調度就轉化成了頂點染色問題或獨立集問題。獨立集的定義如下：

定義1 獨立集：給定圖G＝ （V，E）的一個k 染色，用Vi來表示圖G 中染以第i 色的頂點集合 （i＝1，2，…，k），則圖G 的一個k 染色對應節點集合V 的一個劃分［V1，V2，…，Vk］，其中每個Vi都是獨立集，而圖G 的頂點顏色數k 就是實現這種劃分的最小自然數。

DVCA［9］是一種分布式頂點染色算法，該算法借鑒Brélaz染色策略。Brélaz算法是一種能夠得到接近最優顏色數的集中式頂點染色算法，該算法反復選擇有最小可用顏色數的節點進行染色。在DVCA 中，每個節點 （不包括基站）僅考慮自己在沖突圖中兩跳范圍內的沖突節點的相關信息，計算自己的權值，判斷自己是否為待染色節點，若是則使用最小的可用顏色來為自己染色。網絡中節點獨立運行該算法，利用廣播獲取局部染色信息。最終經過3個階段將網絡中的節點劃分為若干獨立集，每個獨立集中的節點可以同時處于工作狀態，互不干擾。DVCA 運行的輪數為O（degmax）（degmax 為沖突圖的最大節點度），算法所用顏色數最多為degmax＋1。

3.2 TSFA調度算法描述

TSFA 調度算法分為分簇網絡形成、獨立集劃分和優先級調度3 個階段。其中前兩個階段是網絡的啟動時期，該時期算法的性能直接影響網絡的服務質量。分簇網絡形成階段采用DWEHC協議進行分簇，該協議能有效減少網絡中的能量消耗，延長網絡生存期。在網絡拓撲結構建立后，使用前文介紹的DVCA 算法對網絡沖突圖進行獨立集劃分。DVCA 算法能夠最大化獨立集，更好地實現時分復用算法中同一時隙內的空間復用。

定義2 監聽速率：節點監聽速率是在節點ni處產生數據的速率，即單位元時間內節點通過監聽周圍環境所獲得的數據量，用d（ni）表示。

定義3 接收速率：節點接收速率是流經節點ni的數據速率，即單位元時間內ni的鄰居節點發送給ni的數據量，用s（ni）表示。在這一過程中，節點ni可以是轉發節點或者是數據融合節點。

定義4 數據權重：數據權重是衡量節點ni獲得信道優先級的重要標準，用weight（ni）表示。數據權重越大，節點獲得信道的優先級越高。

網絡中任意節點數據權重weight（ni）設置如下

網絡中任意節點記為ni（i∈ ｛1，2，…，n｝）。

經過網絡初期的準備工作，算法正式進入核心階段：優先級調度階段。該階段的主要工作是由簇頭為簇內的獨立集分配時隙。根據前文分析，為了保證網絡的吞吐量和信道共享的公平性，網絡拓撲結構和數據流量分布是需要考慮的兩個重要因素。因此，如果能夠得到獨立集中節點的層次結構和獨立集之間的數據流量大小，無疑能夠更加合理地判斷出各獨立集占有時隙的優先級。這樣，TSFA調度算法時隙分配問題轉化為如式 （2）和式 （3）的priority優先級計算問題

式 （2）中Vi是指染以第i 中顏色的獨立集，priority（Vi）代表此獨立集Vi占有時隙的優先級，level（j）表示獨立集Vi中節點j 的層次數，Ni表示獨立集Vi中的節點數。這種優先權定義綜合了網絡的節點數目和多跳結構等多種因素的影響。

如果考慮數據流量分布等因素，加入數據權重影響因子，則可提出如式 （2）所示的優先級計算方案

式中：Vi——染以第i中顏色的獨立集，weight（j）——獨立集Vi中節點j 的數據權重 （weight（j）的定義詳見定義4），rand（Vi）——一個隨機數，作為調整因子。這種方案充分考慮了網絡中數據流量動態變化的特點，能夠適應網絡中的突發狀況，更好地滿足公平性的要求。

為了實現公平性，簇內每個節點需要周期性維護調度信息表。表內存在信息：節點標識id，節點顏色color，節點層次level，節點產生數據速率d，節點流經數據速率s。信息表組成如下所示：

調度信息表 （Node＿schedule＿info）

Node＿schedule＿info＝ （id，color，level，d，s）

簇內節點將這些信息放在數據包的包頭中，在所屬時隙內將數據包發送出去。這樣調度信息表可以隨著數據包的傳輸到達簇頭節點，保證了TSFA 調度算法的正常運行。

根據以上分析，時分復用調度算法流程如圖2、圖3所示。

3.3 TSFA調度算法舉例

為更好理解TSFA調度算法的工作流程，本文構建一個虛擬應用場景。該場景是一個以數據采集為目的的無線傳感器網絡，網絡中節點監聽周圍環境信息，然后通過多跳模式將信息傳送到基站。為簡化分析，假設網絡中的節點總數為10 （不包括基站節點），網絡拓撲結構如圖4所示。

在此結構圖中，DS是基站節點，節點a和節點f是直接和DS通信的簇頭節點 （兩個簇簡稱為簇a和簇f）。節點b，c，d，e在以節點a為簇頭的簇內，而節點g，h，i，k在以節點f為簇頭的簇內。圖4中實線表示主沖突關系，虛線表示次沖突關系。根據沖突關系應用DVCA［9］染色算法對網絡中的節點進行染色，相同顏色的節點加入同一獨立集。染色結果為簇a形成獨立集 ｛b，e｝， ｛c｝， ｛d｝，簇f形成獨立集 ｛h，i｝，｛g｝，｛k｝。然后簇頭節點和簇內節點分別按照各自的工作流程運行調度算法。簇頭節點根據簇內各節點的數據流量情況，計算各獨立集的優先級，最后按照優先級的順序分配時隙。網絡中各節點的某一周期調度信息見表1，時隙分配情況見表2。

圖2 簇內節點基本工作流程

圖3 簇頭節點基本工作流程

圖4 網絡拓撲結構

表1 節點調度信息

表2 時隙分配情況

4 實驗與分析

本文通過MatLab仿真對滿足公平性的時分復用調度算法TSFA 進行性能分析與評估，并與GCSA 和TRAMA進行性能比較。

實驗中，在邊長100 m 的正方形仿真區域內隨機布置110個節點。Sink節點在網絡監測區域的中心，實驗參數見表3。

表3 實驗參數

仿真實驗從網絡的吞吐量、時延和能量消耗3個性能指標分析TSFA 調度算法的性能，實驗結果如圖5，圖6所示。其中，圖5 （a）為3種算法的吞吐量比較。從圖中可以看出，在算法開始執行階段，由于TSFA 尚未了解網絡中的流量分布，所以TSFA 和GCSA 的吞吐量沒有明顯差異。但是，隨著時間的增加，TSFA 的吞吐量比GCSA 有一定的提高。這是由于在TSFA 調度模式下，簇頭節點通過不斷接收來自簇內各節點的數據權重信息，從而掌握簇內各獨立集的數據流量大小，開始采用第二方案進行優先級調度。從圖中還可以看到，TSFA 和TRAMA 都能維持較高的網絡吞吐量要求，二者在吞吐量性能上優于GCSA算法。圖5 （b）為3 種算法的時延比較。由于TSFA 和TRAMA 在信道利用率方面比GCSA 有著很大的改善，所以隨著時間的增加，GCSA 的時延增加較為明顯。這是因為TSFA 和TRAMA 都采用了基于流量的傳輸調度策略，使數據量大的節點優先占有信道，而無數據或數據量較少的節點進入低能耗模式，有效減少了丟包率及時延。圖5（c）顯示了網絡中總能量的消耗情況。從圖中可以看到，因為TSFA 能夠減少網絡延遲，提高信道利用率，所以能量消耗要大幅低于GCSA。同時，由于TSFA 與TRAMA相比，算法簡單，通信開銷較小，因此，TSFA 的能量消耗要比TRAMA 低。圖6給出了網絡數據流量分布差異變大時3種算法的比較結果。從圖中可以看到，TSFA 在吞吐量的提升和降低延時、能量消耗方面效果更加顯著

實驗結果表明，TSFA 能夠有效提高信道利用率，延長網絡生存時間，且更適用于網絡數據流量分布不均的應用場景。

圖5 WSN 的3種調度算法比較

圖6 WSN 網絡數據流量差異變大時3種調度算法比較

5 結束語

本文給出了一種滿足公平性的無線傳感器網絡時分復用調度算法。其核心思想是利用分簇算法將網絡組織成大小非均勻的簇，然后簇頭通過染色算法將簇內節點劃分成獨立集，最后應用調度算法根據網絡中的流量分布對各個獨立集進行調度。算法在保證節點間數據傳輸不發生沖突的前提下，較好地解決了信道利用的公平性問題。實驗結果表明，算法提高了網絡吞吐量，降低了網絡時延，減少了網絡的能量消耗，延長網絡使用壽命，并且在網絡數據流量差異變大的時候性能更好。

［1］Beel Yick J，Mukherjee B，Ghosal D.Wireless sensor network survey［J］.Computer Networks，2008，52（12）：2292－2330.

［2］HONG Feng，CHU Hongwei，JIN Zongke，et al.Review of recent progress on wireless sensor network applications ［J］.Journal of Computer Research and Development，2010，47（Suppl）：81－87 （in Chinese）.［洪峰，褚紅偉，金宗科，等.無線傳感器網絡應用系統最新進展綜述 ［J］.計算機研究與發展，2010，47 （Suppl）：81－87.］

［3］Hoon K，Sung－Gi M.Priority－based QoS MAC protocol for wireless sensor networks［C］／／Proc of the IEEE International Symposium on Parallel＆Distributed Processiong，2009：1－8

［4］ZHANG Xiaoke，ZENG Jianping，XU Chaonong，et al.Research on MAC scheduling algorithm for wireless network based on distributed graph coloring［J］.Journal of Computer Research and Development，2011，48 （z2）：216－222 （in Chinese）. ［張曉軻，曾健平，徐朝農，等.基于分布式圖染色的無線MAC調度算法研究［J］.計算機研究與發展，2011，48 （z2）：216－222.］

［5］Mahfoudh S，Minet P，Amdouni I.Energy efficient routing and node activity scheduling in the OCARI wireless sensor network ［J］.Future Internet，2010，2 （3）：308－340.

［6］Suriyachai P，Roedig U，Scott A.A survey of MAC protocols for mission－critical applications in wireless sensor networks［J］.Communications Surveys ＆ Tutorials，IEEE，2012，14（2）：240－264.

［7］Rhee I，Warrier A，Aia M，et al.Z－MAC：A hybrid MAC for wireless sensor networks［J］.IEEE／ACM Transactions on Networking，2008，16 （3）：511－524.

［8］Rajendran V，Obraczka K，Garcia－Luna－Aceves JJ.Energyefficient，collision－free medium access control for wireless sensor networks ［J］. Wireless Networks，2006，12 （1）：63－78.

［9］Kang H，Zhao Y，Mei F.A graph coloring based TDMA scheduling algorithm for wireless sensor networks［J］.Wireless Personal Communications，2013，72 （2）：1005－1022.

［10］Sinem Coleri Ergen，Pravin Varaiya.TDMA scheduling algorithms for wireless sensor networks［J］.Wireless Networks，2010，16 （4）：985－997.

［11］Ding P，Holliday JA，Celik A.Distributed energy－efficient hierarchical clustering for wireless sensor networks［M］／／Distributed Computing in Sensor Systems.Berlin：Springer Berlin Heidelberg，2005：322－339.

［12］Tao Shu，Marwan Krunz.Energy－efficient power／rate control and scheduling in hybrid TDMA／CDMA wireless sensor networks ［J］. Computer Networks，2009，53 （9）：1395－1408.

［13］Cardieri P.Modeling interference in wireless Ad Hoc networks［J］.IEEE Communications Surveys＆Tutorials，2010，12 （4），551－572.