WSN 中滿足公平性的時分復(fù)用調(diào)度算法

高 強(qiáng)，李英濤，2，孫大洋，張 婧，2

（1.吉林大學(xué) 計算機(jī)科學(xué)與技術(shù)學(xué)院，吉林 長春130012；2.吉林大學(xué) 符號計算與知識工程教育部重點(diǎn)實(shí)驗(yàn)室，吉林 長春130012；3.吉林大學(xué) 通信工程學(xué)院，吉林 長春130012）

0 引 言

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

無線傳感器網(wǎng)絡(luò)中節(jié)能和數(shù)據(jù)傳輸中的沖突避免問題與MAC協(xié)議密切相關(guān)［3］。MAC 協(xié)議主要負(fù)責(zé)節(jié)點(diǎn)接入無線信道，是其它協(xié)議實(shí)現(xiàn)的基礎(chǔ)，在無線傳感網(wǎng)絡(luò)中起著決定性作用［4］。在MAC協(xié)議中，根據(jù)信道的分配方式，可分為基于TDMA 的時分復(fù)用固定式和基于CSMA 的隨機(jī)競爭式兩種?；跁r分復(fù)用的MAC 協(xié)議為網(wǎng)絡(luò)中的節(jié)點(diǎn)分配獨(dú)立的時隙，以避免節(jié)點(diǎn)間的相互沖突，節(jié)點(diǎn)在不屬于自己的傳輸時隙內(nèi)轉(zhuǎn)入休眠狀態(tài)以減少能量消耗，且能夠在一定程度上保證網(wǎng)絡(luò)傳輸?shù)膶?shí)時性［5］。

本文的設(shè)計目的是在深入分析現(xiàn)有的典型TDMA 調(diào)度算法的基礎(chǔ)上，改進(jìn)并提出一種能夠有效滿足信道分配公平性的方法。

1 相關(guān)工作

為了滿足信道分配的需求，研究人員已經(jīng)提出了大量有關(guān)TDMA 的算法［6］。

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

文獻(xiàn) ［8］中提出了一種流量自適應(yīng)介質(zhì)訪問協(xié)議TRAMA，該協(xié)議由相鄰節(jié)點(diǎn)協(xié)議、傳輸時間安排交換協(xié)議和自適應(yīng)選舉算法組成，根據(jù)相鄰區(qū)域的節(jié)點(diǎn)流量信息來選擇當(dāng)前時隙的發(fā)送節(jié)點(diǎn)和接收節(jié)點(diǎn)。TRAMA 通信開銷小，但是延遲較長，比較適用于周期性數(shù)據(jù)采集和監(jiān)測無線傳感器網(wǎng)絡(luò)方面的應(yīng)用。

文獻(xiàn) ［9］中提出了一種基于圖染色理論的時分復(fù)用調(diào)度算法GCSA，該算法分為兩個階段：染色階段和調(diào)度階段。染色階段借鑒Brélaz染色策略，提出了一種分布式頂點(diǎn)染色算法DVCA，以達(dá)到接近最優(yōu)的獨(dú)立集劃分。調(diào)度階段根據(jù)染色階段得到的染色結(jié)果使用基于優(yōu)先權(quán)的調(diào)度策略為獨(dú)立集分配時隙。該算法具有可擴(kuò)展性且能得到較少的顏色以最大化獨(dú)立集，但是調(diào)度策略解決網(wǎng)絡(luò)的公平性問題有待改進(jìn)。

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

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

2 網(wǎng)絡(luò)模型

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

根據(jù)網(wǎng)絡(luò)特點(diǎn)作出如下假設(shè)：

（1）數(shù)據(jù)匯聚點(diǎn)DS位于一個方形觀測區(qū)域A 的內(nèi)部。所有節(jié)點(diǎn)在部署后不再發(fā)生位置移動。

（2）使用DWEHC［11］分簇協(xié)議得到所需要的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)。分簇后的網(wǎng)絡(luò)結(jié)構(gòu)如圖1所示。

圖1 分簇網(wǎng)絡(luò)結(jié)構(gòu)

（3）簇內(nèi)節(jié)點(diǎn)采用多跳模式使用基于時分復(fù)用的MAC協(xié)議與簇頭節(jié)點(diǎn)通信，簇頭節(jié)點(diǎn)為簇內(nèi)節(jié)點(diǎn)通信分配CDMA 編碼以避免簇間沖突，而簇頭節(jié)點(diǎn)以單跳模式使用基于競爭的MAC協(xié)議來向基站節(jié)點(diǎn)傳輸數(shù)據(jù)［12］。

（4）每個節(jié)點(diǎn)都是同構(gòu)的，且有一個唯一的標(biāo)識（ID）。

（5）網(wǎng)絡(luò)中的節(jié)點(diǎn)可以自由調(diào)整發(fā)射功率，支持雙向數(shù)據(jù)通信［13］。

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

（7）無線傳感器網(wǎng)絡(luò)中節(jié)點(diǎn)間的傳輸沖突分為主沖突和次沖突。本文使用文獻(xiàn) ［9］中得到?jīng)_突圖的方法定義節(jié)點(diǎn)間的沖突關(guān)系。

3 算法介紹與相關(guān)定義

3.1 DVCA染色算法描述

將大規(guī)模無線自組織網(wǎng)絡(luò)抽象成圖G＝ （V，E）結(jié)構(gòu)，圖中的點(diǎn)集V 代表網(wǎng)絡(luò)中的鏈路，這樣把一個無線網(wǎng)絡(luò)抽象為圖，進(jìn)而節(jié)點(diǎn)調(diào)度就轉(zhuǎn)化成了頂點(diǎn)染色問題或獨(dú)立集問題。獨(dú)立集的定義如下：

定義1 獨(dú)立集：給定圖G＝ （V，E）的一個k 染色，用Vi來表示圖G 中染以第i 色的頂點(diǎn)集合 （i＝1，2，…，k），則圖G 的一個k 染色對應(yīng)節(jié)點(diǎn)集合V 的一個劃分［V1，V2，…，Vk］，其中每個Vi都是獨(dú)立集，而圖G 的頂點(diǎn)顏色數(shù)k 就是實(shí)現(xiàn)這種劃分的最小自然數(shù)。

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

3.2 TSFA調(diào)度算法描述

TSFA 調(diào)度算法分為分簇網(wǎng)絡(luò)形成、獨(dú)立集劃分和優(yōu)先級調(diào)度3 個階段。其中前兩個階段是網(wǎng)絡(luò)的啟動時期，該時期算法的性能直接影響網(wǎng)絡(luò)的服務(wù)質(zhì)量。分簇網(wǎng)絡(luò)形成階段采用DWEHC協(xié)議進(jìn)行分簇，該協(xié)議能有效減少網(wǎng)絡(luò)中的能量消耗，延長網(wǎng)絡(luò)生存期。在網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)建立后，使用前文介紹的DVCA 算法對網(wǎng)絡(luò)沖突圖進(jìn)行獨(dú)立集劃分。DVCA 算法能夠最大化獨(dú)立集，更好地實(shí)現(xiàn)時分復(fù)用算法中同一時隙內(nèi)的空間復(fù)用。

定義2 監(jiān)聽速率：節(jié)點(diǎn)監(jiān)聽速率是在節(jié)點(diǎn)ni處產(chǎn)生數(shù)據(jù)的速率，即單位元時間內(nèi)節(jié)點(diǎn)通過監(jiān)聽周圍環(huán)境所獲得的數(shù)據(jù)量，用d（ni）表示。

定義3 接收速率：節(jié)點(diǎn)接收速率是流經(jīng)節(jié)點(diǎn)ni的數(shù)據(jù)速率，即單位元時間內(nèi)ni的鄰居節(jié)點(diǎn)發(fā)送給ni的數(shù)據(jù)量，用s（ni）表示。在這一過程中，節(jié)點(diǎn)ni可以是轉(zhuǎn)發(fā)節(jié)點(diǎn)或者是數(shù)據(jù)融合節(jié)點(diǎn)。

定義4 數(shù)據(jù)權(quán)重：數(shù)據(jù)權(quán)重是衡量節(jié)點(diǎn)ni獲得信道優(yōu)先級的重要標(biāo)準(zhǔn)，用weight（ni）表示。數(shù)據(jù)權(quán)重越大，節(jié)點(diǎn)獲得信道的優(yōu)先級越高。

網(wǎng)絡(luò)中任意節(jié)點(diǎn)數(shù)據(jù)權(quán)重weight（ni）設(shè)置如下

網(wǎng)絡(luò)中任意節(jié)點(diǎn)記為ni（i∈ ｛1，2，…，n｝）。

經(jīng)過網(wǎng)絡(luò)初期的準(zhǔn)備工作，算法正式進(jìn)入核心階段：優(yōu)先級調(diào)度階段。該階段的主要工作是由簇頭為簇內(nèi)的獨(dú)立集分配時隙。根據(jù)前文分析，為了保證網(wǎng)絡(luò)的吞吐量和信道共享的公平性，網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)和數(shù)據(jù)流量分布是需要考慮的兩個重要因素。因此，如果能夠得到獨(dú)立集中節(jié)點(diǎn)的層次結(jié)構(gòu)和獨(dú)立集之間的數(shù)據(jù)流量大小，無疑能夠更加合理地判斷出各獨(dú)立集占有時隙的優(yōu)先級。這樣，TSFA調(diào)度算法時隙分配問題轉(zhuǎn)化為如式 （2）和式 （3）的priority優(yōu)先級計算問題

式 （2）中Vi是指染以第i 中顏色的獨(dú)立集，priority（Vi）代表此獨(dú)立集Vi占有時隙的優(yōu)先級，level（j）表示獨(dú)立集Vi中節(jié)點(diǎn)j 的層次數(shù)，Ni表示獨(dú)立集Vi中的節(jié)點(diǎn)數(shù)。這種優(yōu)先權(quán)定義綜合了網(wǎng)絡(luò)的節(jié)點(diǎn)數(shù)目和多跳結(jié)構(gòu)等多種因素的影響。

如果考慮數(shù)據(jù)流量分布等因素，加入數(shù)據(jù)權(quán)重影響因子，則可提出如式 （2）所示的優(yōu)先級計算方案

式中：Vi——染以第i中顏色的獨(dú)立集，weight（j）——獨(dú)立集Vi中節(jié)點(diǎn)j 的數(shù)據(jù)權(quán)重 （weight（j）的定義詳見定義4），rand（Vi）——一個隨機(jī)數(shù)，作為調(diào)整因子。這種方案充分考慮了網(wǎng)絡(luò)中數(shù)據(jù)流量動態(tài)變化的特點(diǎn)，能夠適應(yīng)網(wǎng)絡(luò)中的突發(fā)狀況，更好地滿足公平性的要求。

為了實(shí)現(xiàn)公平性，簇內(nèi)每個節(jié)點(diǎn)需要周期性維護(hù)調(diào)度信息表。表內(nèi)存在信息：節(jié)點(diǎn)標(biāo)識id，節(jié)點(diǎn)顏色color，節(jié)點(diǎn)層次level，節(jié)點(diǎn)產(chǎn)生數(shù)據(jù)速率d，節(jié)點(diǎn)流經(jīng)數(shù)據(jù)速率s。信息表組成如下所示：

調(diào)度信息表 （Node＿schedule＿info）

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

簇內(nèi)節(jié)點(diǎn)將這些信息放在數(shù)據(jù)包的包頭中，在所屬時隙內(nèi)將數(shù)據(jù)包發(fā)送出去。這樣調(diào)度信息表可以隨著數(shù)據(jù)包的傳輸?shù)竭_(dá)簇頭節(jié)點(diǎn)，保證了TSFA 調(diào)度算法的正常運(yùn)行。

根據(jù)以上分析，時分復(fù)用調(diào)度算法流程如圖2、圖3所示。

3.3 TSFA調(diào)度算法舉例

為更好理解TSFA調(diào)度算法的工作流程，本文構(gòu)建一個虛擬應(yīng)用場景。該場景是一個以數(shù)據(jù)采集為目的的無線傳感器網(wǎng)絡(luò)，網(wǎng)絡(luò)中節(jié)點(diǎn)監(jiān)聽周圍環(huán)境信息，然后通過多跳模式將信息傳送到基站。為簡化分析，假設(shè)網(wǎng)絡(luò)中的節(jié)點(diǎn)總數(shù)為10 （不包括基站節(jié)點(diǎn)），網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)如圖4所示。

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

圖2 簇內(nèi)節(jié)點(diǎn)基本工作流程

圖3 簇頭節(jié)點(diǎn)基本工作流程

圖4 網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)

表1 節(jié)點(diǎn)調(diào)度信息

表2 時隙分配情況

4 實(shí)驗(yàn)與分析

本文通過MatLab仿真對滿足公平性的時分復(fù)用調(diào)度算法TSFA 進(jìn)行性能分析與評估，并與GCSA 和TRAMA進(jìn)行性能比較。

實(shí)驗(yàn)中，在邊長100 m 的正方形仿真區(qū)域內(nèi)隨機(jī)布置110個節(jié)點(diǎn)。Sink節(jié)點(diǎn)在網(wǎng)絡(luò)監(jiān)測區(qū)域的中心，實(shí)驗(yàn)參數(shù)見表3。

表3 實(shí)驗(yàn)參數(shù)

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

實(shí)驗(yàn)結(jié)果表明，TSFA 能夠有效提高信道利用率，延長網(wǎng)絡(luò)生存時間，且更適用于網(wǎng)絡(luò)數(shù)據(jù)流量分布不均的應(yīng)用場景。

圖5 WSN 的3種調(diào)度算法比較

圖6 WSN 網(wǎng)絡(luò)數(shù)據(jù)流量差異變大時3種調(diào)度算法比較

5 結(jié)束語

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

［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）.［洪峰，褚紅偉，金宗科，等.無線傳感器網(wǎng)絡(luò)應(yīng)用系統(tǒng)最新進(jìn)展綜述 ［J］.計算機(jī)研究與發(fā)展，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）. ［張曉軻，曾健平，徐朝農(nóng)，等.基于分布式圖染色的無線MAC調(diào)度算法研究［J］.計算機(jī)研究與發(fā)展，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.