一種時分簇調(diào)度算法的實現(xiàn)*

任苗苗，范書瑞，2*，王悅良

（1.河北工業(yè)大學(xué)電子信息工程學(xué)院，天津 300401；2.昆士蘭大學(xué)信息技術(shù)與電氣工程系，昆士蘭 4072，澳大利亞）

一種時分簇調(diào)度算法的實現(xiàn)*

任苗苗1，范書瑞1，2*，王悅良1

（1.河北工業(yè)大學(xué)電子信息工程學(xué)院，天津 300401；2.昆士蘭大學(xué)信息技術(shù)與電氣工程系，昆士蘭 4072，澳大利亞）

無線傳感器網(wǎng)絡(luò)是一種典型的資源受限系統(tǒng)，研究信道和時隙在內(nèi)的資源分配方法，對提高網(wǎng)絡(luò)性能保障服務(wù)質(zhì)量具有重要意義。為解決智慧醫(yī)療系統(tǒng)中傳感網(wǎng)絡(luò)結(jié)構(gòu)不固定，服務(wù)質(zhì)量無法保障問題，構(gòu)建了一種非平衡的簇樹結(jié)構(gòu)，采用可避免碰撞、保證傳輸時延的時分簇調(diào)度算法進(jìn)行傳輸任務(wù)的分配，將資源分配結(jié)果在TinyOS系統(tǒng)中進(jìn)行實現(xiàn)，并采用CC2530平臺進(jìn)行驗證。為便于修改數(shù)據(jù)流參數(shù)，使調(diào)度的結(jié)果更加直觀，設(shè)計了圖形用戶界面。結(jié)果表明這種時分簇調(diào)度算法可以保證非平衡結(jié)構(gòu)無線傳感網(wǎng)絡(luò)通信質(zhì)量，為大規(guī)模簇樹網(wǎng)絡(luò)提供有效的服務(wù)保障。

無線傳感器網(wǎng)絡(luò)；資源分配；時分簇調(diào)度；TinyOS

近年來，物聯(lián)網(wǎng)技術(shù)的快速發(fā)展，使無線傳感器網(wǎng)絡(luò)進(jìn)一步得到普及。簇樹結(jié)構(gòu)是無線傳感網(wǎng)絡(luò)的一種常用網(wǎng)絡(luò)，其中的源數(shù)據(jù)流通過各個路由遍歷不同的簇，最終流入端節(jié)點。在相鄰的簇間可能會發(fā)生數(shù)據(jù)的碰撞而使通信失敗，這限制了網(wǎng)絡(luò)規(guī)模，其關(guān)鍵是簇間調(diào)度和沖突避免無法很好的解決。MAC（Media Access Control，媒體接入控制）協(xié)議負(fù)責(zé)為網(wǎng)絡(luò)中的各個節(jié)點分配無線通信資源的是，對整個網(wǎng)絡(luò)的性能有直接影響。文獻(xiàn)［1］對典型調(diào)度方法進(jìn)行了分析，傳統(tǒng)的MAC協(xié)議存在嚴(yán)重的沖突重傳，不能滿足資源有限、能量有限的無線傳感網(wǎng)絡(luò)的要求。針對MAC層的資源調(diào)度衍生了一系列解決算法。文獻(xiàn)［2］采用自觸發(fā)采樣策略減少網(wǎng)絡(luò)利用和能耗損耗的同時，確保了網(wǎng)絡(luò)性能。文獻(xiàn)［3］針對能量敏感問題設(shè)計了模型預(yù)測控制，確保WSN魯棒性。文獻(xiàn)［4］采用自適應(yīng)GTS分配方法用于保證網(wǎng)絡(luò)實時特性。這些從理論角度證明了IEEE802.15.4的GTS分配機(jī)制適用于現(xiàn)代工業(yè)網(wǎng)絡(luò)控制系統(tǒng)。

GTS機(jī)制為節(jié)點提供了一種實時服務(wù)保障，滿足對時間敏感場合的應(yīng)用。但是如何均衡網(wǎng)絡(luò)規(guī)模和網(wǎng)絡(luò)性能，沒有得到很好解決。針對不同的網(wǎng)絡(luò)結(jié)構(gòu)，研究人員提出了各種方法。文獻(xiàn)［5］針對可分負(fù)載星型無線傳感器網(wǎng)，提出以能耗均衡為目的的調(diào)度算法。在文獻(xiàn)［6］中提出一種利用區(qū)分服務(wù)的GTS統(tǒng)籌算法來調(diào)度節(jié)點資源，但開銷隨網(wǎng)絡(luò)的規(guī)模成幾何級數(shù)增長，且算法對全網(wǎng)的時間同步要求過于苛刻，不適合用于大規(guī)模網(wǎng)絡(luò)。文獻(xiàn)［7］對傳統(tǒng)的CSMA/CD做了改進(jìn)，根據(jù)下行鄰居節(jié)點數(shù)進(jìn)行分組，通過組的有序競爭減輕碰撞問題。文獻(xiàn)［8］設(shè)計了一種自適應(yīng)的MAC層調(diào)度算法，根據(jù)路徑信息判斷數(shù)據(jù)量的大小從而合理分配時隙。文獻(xiàn)［9］采用圖論方法設(shè)計了動態(tài)調(diào)度算法的任務(wù)分配策略，減少任務(wù)間等待時間和通信時間。但是這些方法都不能克服信道的爭用，無法滿足工業(yè)應(yīng)用實時性的要求。

文獻(xiàn)［10］提出了針對IEEE802.15.4協(xié)議超幀結(jié)構(gòu)的時分調(diào)度算法（TDCS），對簇樹網(wǎng)絡(luò)中不同節(jié)點的超幀區(qū)間進(jìn)行了調(diào)度，有效解決同步信標(biāo)幀之間的沖突。文獻(xiàn)［11-12］研究了IEEE802.15.4的GTS機(jī)制，為節(jié)點提供了一種實時服務(wù)保障，滿足對時間敏感場合的應(yīng)用，可預(yù)測每個應(yīng)用節(jié)點的最糟糕性能。這些都是已給出平衡簇樹結(jié)構(gòu)的無線傳感器網(wǎng)絡(luò)中。但是更多的應(yīng)用場景是非平衡結(jié)構(gòu)，上面的方法容易造成資源極大浪費，本文解決非平衡結(jié)構(gòu)網(wǎng)絡(luò)資源分配問題。

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

在簇樹拓?fù)浣Y(jié)構(gòu)中，由于每個節(jié)點只與其設(shè)定好的父路由器和子節(jié)點通信，所以擁有固定的多跳通信路徑。每個簇的活動在時間上式周期的，在每個活動周期都可以分為兩部分：活躍期和非活躍期。每個除根節(jié)點外的路由器都可以屬于兩個簇，一次作為子節(jié)點，一次作為簇頭節(jié)點。因此，當(dāng)這兩個簇任意一個處于活躍期時，路由器都會被喚醒，否則則進(jìn)入低功耗模式，以節(jié)省能耗。針對智慧醫(yī)療中的不平衡網(wǎng)絡(luò)結(jié)構(gòu)，設(shè)計了如圖1所示的非平衡的簇樹結(jié)構(gòu)網(wǎng)絡(luò)。

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

在TDCS算法中，為了描述非平衡簇樹網(wǎng)絡(luò)結(jié)構(gòu)，將網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)用矩陣A=（aij）的形式表述。如果路由器i是路由器j的子節(jié)點，則aij=1，否則aij=0。矩陣A的維數(shù)等于網(wǎng)絡(luò)中總的節(jié)點數(shù)。因此上述簇樹結(jié)構(gòu)的矩陣表示為：

2 任務(wù)分配及算法實現(xiàn)

本文采用的TDCS算法具有兩種約束形式：相對于沖突域的簇資源約束和數(shù)據(jù)流的時序約束。因此，任務(wù)的設(shè)置包括一組簇任務(wù)和一組僅反映時間限制的虛擬任務(wù)。

2.1 任務(wù)定義與分配

簇任務(wù)Ti與網(wǎng)絡(luò)結(jié)構(gòu)中每一簇i相對應(yīng)。當(dāng)簇處于活躍期時，該簇的任務(wù)處理時間等于簇的超幀區(qū)間長度SD。每一個虛擬任務(wù)對應(yīng)著給定數(shù)據(jù)流在給定簇中的活動。用 pi表示簇任務(wù)Ti的處理時間。 pi包括簇i活躍期中的競爭接入期CAP、所有接收信息方向的GTS和發(fā)送信息方向的GTS。

每個數(shù)據(jù)流存在一個或多個源節(jié)點和確定的一個匯聚節(jié)點。在本文中根據(jù)網(wǎng)絡(luò)簇樹圖1定義了兩個數(shù)據(jù)流，其具體參數(shù)如表1所示。

表1 數(shù)據(jù)流參數(shù)

根據(jù)網(wǎng)絡(luò)簇樹結(jié)構(gòu)可知，數(shù)據(jù)流1由源節(jié)點12、13分別遍經(jīng)簇4簇1，簇5簇2簇1，最后進(jìn)入簇3的端節(jié)點。數(shù)據(jù)流2由源節(jié)點6、10分別遍經(jīng)簇6，簇3 簇1，在簇2匯聚并到達(dá)端節(jié)點9。

2.2 任務(wù)調(diào)度

調(diào)度問題可以定義為尋找一個可用的調(diào)度（s1、s2、···、sn）來滿足時序和資源約束。定義變量si為任務(wù)Ti的啟動時間持續(xù)長度。不同任務(wù)將最大調(diào)度周期BI分割給不同si。

si可以用下式表示：

該調(diào)度算法采用整數(shù)線性規(guī)劃（ILP）實現(xiàn)。得到二元的結(jié)果xij。該規(guī)劃的約束條件如下：

通過上述規(guī)劃得到的變量xij定義了任務(wù)Ti和Tj間的相互關(guān)系：

當(dāng)xij=0，則任務(wù)Tj在Ti后；當(dāng)xij=1時，則任務(wù)Ti在Tj后。

pj是任務(wù)Tj的處理時間，vij表示優(yōu)先約束的偏移量。wij表示任務(wù)先后順序的一個參量，如果wij大于零，則表示任務(wù)Ti的開始時間si要比任務(wù)Tj的開始時間sj至少延遲wij，wij小于零，則提前相應(yīng)wij。

3 硬件實現(xiàn)

CC2530是一個兼容2.4GHz IEEE802.15.4的真正的片上系統(tǒng)，能以教低的成本建立大規(guī)模網(wǎng)絡(luò)。由于TinyOS現(xiàn)階段不支持CC2530節(jié)點，在組網(wǎng)前首先要設(shè)計CC2530相關(guān)組件，完成TinyOS操作系統(tǒng)在CC2530上的移植。TinyOS具有層次性的架構(gòu)，其移植性直接與最底層的硬件抽象組件相關(guān)。

3.1 系統(tǒng)移植

系統(tǒng)移植包括CC2530的寄存器聲明和組件移植。在ioCC2530.h文件聲明了CC2530部寄存器配置，對應(yīng)的timer、adc、radio等文件夾內(nèi)包含了CC2530下對應(yīng)時鐘、射頻、串口通信等功能的組件。

Timer組件是一個定時器組件，其Timer接口用來觸發(fā)事件。先根據(jù)CC2530芯片內(nèi)部定時器部分?jǐn)?shù)據(jù)資料定義各層需要定制的接口和組件列表；然后用nesC語言編寫上述各層列表中定義的接口、組件的代碼和timer.h文件，并一起存放到timer文件夾中。

Radio組件是TinyOS的射頻組件，提供Packet、Receive、AMSend和SpiltControl接口。Packet用來實現(xiàn)數(shù)據(jù)包的管理，Receive具有數(shù)據(jù)包的接收功能，AMSend具有發(fā)送數(shù)據(jù)包的功能，SpiltControl用來控制天線的狀態(tài)，負(fù)責(zé)天線的開啟和關(guān)閉。

3.2 信道掃描

為了創(chuàng)建良好的運行環(huán)境，需要掃描信道。通過獲取CC2530的RSSI值，將RSSI數(shù)據(jù)自動附加到接收到的數(shù)據(jù)幀中。在處理接收數(shù)據(jù)幀的函數(shù)中對消息元結(jié)構(gòu)體進(jìn)行定義，設(shè)定有關(guān)RSSI的位定義。當(dāng)接收完整的一幀數(shù)據(jù)時，只需要讀取幀檢測序列字段中的內(nèi)容就可以獲取RSSI的數(shù)值。

對于CC2530而言，接收信息的RSSI為只讀字段。在接收到數(shù)據(jù)包后，程序自動觸發(fā)Receive函數(shù)，在接收函數(shù)中調(diào)用上述定義的getRssi函數(shù)，即能返回接收信號的RSSI值，從而實現(xiàn)對RSSI的監(jiān)控。關(guān)鍵接收函數(shù)：

3.3 計算結(jié)果應(yīng)用

根據(jù)各節(jié)點實現(xiàn)的不同功能，將節(jié)點分為端節(jié)點、路由器、匯聚節(jié)點三種。對三種不同功能的節(jié)點分別進(jìn)行程序設(shè)計。端節(jié)點負(fù)責(zé)發(fā)送數(shù)據(jù)；匯聚節(jié)點負(fù)責(zé)接收各節(jié)點發(fā)送來的數(shù)據(jù)；路由器從端節(jié)點接收數(shù)據(jù)后觸發(fā)發(fā)送功能，將收到的數(shù)據(jù)向上轉(zhuǎn)發(fā)給其由TDCS算法決定的父節(jié)點。對不同的傳感器節(jié)點，在發(fā)送指令A(yù)MSend.send函數(shù)中根據(jù)TDCS計算結(jié)果，指定其發(fā)送的目標(biāo)節(jié)點編號，關(guān)鍵代碼如下：

連接好硬件節(jié)點，在cygwin命令窗口中針對節(jié)點類型進(jìn)入apps/CC2530/TDCS下對應(yīng)的文件夾，將程序編譯下載到對應(yīng)節(jié)點上。在匯聚節(jié)點上連接串口即可觀察到實驗結(jié)果。

4 測試效果

按照表1中給出的參數(shù)設(shè)定用戶界面中的輸入值，數(shù)據(jù)流1的源節(jié)點為12、13，匯聚節(jié)點為11；數(shù)據(jù)流2的源節(jié)點為6、10，匯聚節(jié)點為9。點擊Calculate運行程序。根據(jù)調(diào)度結(jié)果顯示，數(shù)據(jù)流1中從源節(jié)點12到匯聚節(jié)點11的傳輸依次激活簇4、1、3；數(shù)據(jù)流1中從源節(jié)點13到匯聚節(jié)點11的傳輸依次激活簇5、簇2、簇1、簇3；數(shù)據(jù)流2中從源節(jié)點10到匯聚節(jié)點9的傳輸依次激活簇3、簇1、簇2。如圖2所示。

圖2 數(shù)據(jù)流傳輸結(jié)果

同時可以觀察到，由于兩個數(shù)據(jù)流都沒有經(jīng)過簇6，所以簇6一直處于非活躍期，即簇6的簇任務(wù)T6的處理時間 p6=0。各簇激活的時序，從而決定了各數(shù)據(jù)流任務(wù)的執(zhí)行時間。在第一時間段內(nèi)簇4、簇5被同時激活，第二時間段內(nèi)簇1處于活躍期，第3時間段激活簇3，第4時間段激活簇2。如圖3所示。

圖3 調(diào)度結(jié)果端到端延時

通過觀察得到的端到端延時值可以發(fā)現(xiàn)，采TDCS調(diào)度算法后有了明顯的改善，滿足了簇樹網(wǎng)絡(luò)通信的低功耗與沖突避免的要求，能夠用于保證非平衡結(jié)構(gòu)無線傳感網(wǎng)絡(luò)通信質(zhì)量。

5 結(jié)論

為了改善非平衡簇樹網(wǎng)絡(luò)通信中的延時與能耗問題，本文應(yīng)用了時分簇調(diào)度（TDCS）算法，研究了簇樹結(jié)構(gòu)的無線傳感器網(wǎng)絡(luò)的通信機(jī)制，并對

TDCS算法進(jìn)行仿真，設(shè)計了GUI圖形用戶界面。使用TinyOS的nesC語言編寫程序，將仿真得到的調(diào)度結(jié)果在CC2530硬件節(jié)點上實現(xiàn)。由于非平衡結(jié)構(gòu)簇樹網(wǎng)絡(luò)通信時各簇間歇處于活躍期或休眠期，

TDCS算法給出了一個最佳的時序調(diào)度方案，得到各簇活躍期的起始時間與延續(xù)區(qū)間。解決了無線傳感器網(wǎng)絡(luò)的降低能耗和沖突避免問題，提高了網(wǎng)絡(luò)性能。

［1］ 張曉玲，梁煒，于海斌，等.無線傳感器網(wǎng)絡(luò)傳輸調(diào)度方法綜述［J］.通信學(xué)報，2012，33（5）：143-157.

［2］ Tiberi U，F(xiàn)ischione C，Johansson K.H.Energy-Efficient SamPling of Networked cControl Systems over IEEE 802.15.4 Wireless Networks［J］.Automatica，2013，49：712-724.

［3］ Daniele Bernardini，Alberto Bemporad.Energy-Aware Robust Model Predictive Control Based on Noisy Wireless Sensors［J］.Automatica，2012，48：36-44.

［4］ Feng Xia，Ruonan Hao，Jie Li，et al.Adaptive GTS Allocation in IEEE 802.15.4 for Real-Time Wireless Sensor Network［J］.Journal of Systems Architecture，2013，59：1231-1242.

［5］ 劉端陽，暴占兵，程珍.一種可分負(fù)載WSN的能耗均衡負(fù)載調(diào)度算法［J］.傳感技術(shù)學(xué)報，2014，27（2）：225-232.

［6］ 葉雪梅，朱云杰，蔡艷寧，等.無線簇樹網(wǎng)下的GTS時隙調(diào)度算法［J］.傳感器與微系統(tǒng)，2014，33（7）：133-136.

［7］ 趙小超，鄭明才，廖瑞華.基于有序競爭的傳感器網(wǎng)絡(luò)的MAC協(xié)議［J］.計算機(jī)工程與應(yīng)用，2012，48（18）：76-80.

［8］ 丁海霞.傳感器網(wǎng)絡(luò)中一種實時的自適應(yīng)時隙調(diào)度算法［J］.計算機(jī)工程與應(yīng)用，2010，46（22）：110-112.

［9］ 高治軍，王洪玉，王鑫，等.智能建筑室內(nèi)環(huán)境分布式可計算WSN任務(wù)調(diào)度研究［J］.傳感技術(shù)學(xué)報，2014，27（3）：378-382.

［10］Anis Koubaa，Andre Cunha，Mario Alves，et al.TDBS：A Time Di-Vision Beacon Scheduling Mechanism for Zigbee Cluster-Tree Wireless Sensor Networks［J］.Real-Time Systems，2008，40（3）：321-354.

［11］Jurcik Petr，Koubaa Anis，Severino Ricardo，et al.Dimensioning and Worst-Case Analysis of Cluster-Tree Sensor Networks［J］. ACM Transactions on Sensor Networks，2010，7（2）：1-47.

［12］Hanzalek Z，Jurcik P.Energy Efficient Scheduling for Cluster-tree Wireless Sensor Networks with Time-Bounded Data Flows：Application to IEEE 802.15.4/ZigBee［J］.IEEE Transactions on Industrial Informatics，2010，6（3）：438-450.

任苗苗（1992-），女，本科，就讀河北工業(yè)大學(xué)電子信息工程專業(yè)，研究方向網(wǎng)絡(luò)資源分配方法，pingshan20@163.com；

范書瑞（1979-），男，講師，博士，研究方向無線傳感器網(wǎng)絡(luò)和嵌入式系統(tǒng)，fansr@hebut.edu.cn。

The Implementation of a Division Cluster Scheduling Algorithm*

REN Miaomiao1，F(xiàn)AN Shurui1，2*，WANG Yueliang1
（1.School of Electric Information Engineering，Hebei University of Technology，Tianjin 300401，China；2.Information Technology and Electrical Engineering，The University of Queensland，Queensland 4072，Australia）

As a typical resource constrained system，Wireless Sensor Network（WSN）can be significantly improved the performance of guarantee quality of service（QoS）by effective resource allocation，including channel and time slot.But thestructureisnotfixedinsmartmedicalsystem，whichcanleadtotheuncertaintyservicequality.Anon-balancedclustertree structure is presentforovercoming the collision and uncertain delay，taking into accountthe allocation oftraffic. The resource parameter is implemented in TinyOS system，which be verified by CC2530 platform.And Graphical User Interface is designed for modifying data flow parameters and inspecting scheduling results.The experimental results show that this cluster tree scheduling algorithm can ensure the non-balanced structure of network quality，and provide theeffectiveserviceguaranteeforlarge-scaleclustertreenetwork.

wireless sensor network；resource allocation；division cluster scheduling algorithm；TinyOS EEACC：6250

TP273

A

1004-1699（2015）07-1073-05

10.3969/j.issn.1004-1699.2015.07.022

項目來源：河北省自然科學(xué)青年基金項目（F2013202102）；河北省科學(xué)研究與發(fā)展計劃項目（11213566）；國家級大學(xué)生創(chuàng)新創(chuàng)業(yè)訓(xùn)練計劃立項項目（201310080009，201410080006）

2014-11-19 修改日期：2015-04-03