6TiSCH分布式網(wǎng)絡(luò)調(diào)度

葉小林

(上海理工大學(xué) 光電信息與計(jì)算機(jī)工程學(xué)院，上海 200093)

0 引言

目前，國(guó)外已經(jīng)成立了6TiSCH工作組(WG)[1-3]。6TiSCH工作組(WG)將TSCH功能與6LoWPAN、ROLL標(biāo)準(zhǔn)化工作及建議聯(lián)系起來(lái)。詳細(xì)地講，它將定義一個(gè)開放的基于標(biāo)準(zhǔn)的架構(gòu)，盡可能重用現(xiàn)有協(xié)議，如鄰居發(fā)現(xiàn)(ND)[4]、邊界路由、分布式網(wǎng)絡(luò)調(diào)度(OTF)[5-6]和路由問(wèn)題(RPL)[7]等。時(shí)隙跳頻(TSCH)模式是低功耗有損網(wǎng)絡(luò)(LLN)最新一代超低功耗和可靠網(wǎng)絡(luò)解決方案，其核心是采用時(shí)間同步媒體接入技術(shù)，實(shí)現(xiàn)超低功耗、信道跳頻和高可靠性[8]。

IEEE802.15.4e標(biāo)準(zhǔn)沒(méi)有定義如何構(gòu)建調(diào)度表，也沒(méi)有強(qiáng)調(diào)如何與網(wǎng)絡(luò)流量要求相匹配[9]。OTF帶寬預(yù)留模塊起到補(bǔ)充作用,它用一個(gè)分布式方法調(diào)整預(yù)定帶寬與網(wǎng)絡(luò)要求。OTF決定何時(shí)添加/刪除單元格(cell)，然后6Top子層對(duì)6TiSCH時(shí)間表進(jìn)行適當(dāng)更改[10]。本文重點(diǎn)是改進(jìn)分布式調(diào)度算法[11-13]，主要為了解決多鄰居之間信息交流、網(wǎng)絡(luò)中突發(fā)流量問(wèn)題和多跳網(wǎng)絡(luò)中廣播問(wèn)題而設(shè)計(jì)。 RPL(低功耗和有損網(wǎng)絡(luò)的路由協(xié)議)將網(wǎng)絡(luò)組織為DODAG拓?fù)浣Y(jié)構(gòu)(面向目的的有向無(wú)環(huán)圖)，每個(gè)節(jié)點(diǎn)生成的數(shù)據(jù)被轉(zhuǎn)發(fā)到其根。調(diào)度算法因此試圖沿著RPL路由創(chuàng)建有效的6TSCH調(diào)度。本文主要貢獻(xiàn)在于：通過(guò)優(yōu)化調(diào)度算法延長(zhǎng)網(wǎng)絡(luò)整體壽命；使用共享信元減小網(wǎng)絡(luò)中的沖突。

1 6TiSCH調(diào)度機(jī)制

6TiSCH允許操作子層(6Top)構(gòu)建并維護(hù)高效的確定性時(shí)間-頻率調(diào)度。6TiSCH網(wǎng)絡(luò)中的節(jié)點(diǎn)遵循時(shí)分多址(TDMA)時(shí)間表進(jìn)行通信，其中時(shí)隙提供分配給鄰居節(jié)點(diǎn)之間通信的帶寬單位。6TiSCH操作子層(6Top)是6TiSCH架構(gòu)中一個(gè)邏輯鏈路層，提供6TiSCH中MAC層(IEEE 802.15.4)IP鏈路的抽象。6Top層支持兩步和三步6Top事務(wù)用于鄰居之間的單元格(cell)協(xié)商，目前應(yīng)用基于兩步6Top協(xié)商，可以擴(kuò)展為三步協(xié)商。調(diào)度功能調(diào)用6Top層對(duì)內(nèi)存中數(shù)據(jù)單元格進(jìn)行ADD/ DELETE單元格調(diào)整，以滿足動(dòng)態(tài)帶寬需求。根據(jù)帶寬要求，執(zhí)行以下步驟:①檢查現(xiàn)有6TiSCH時(shí)間表以確定可用空閑單元格滿足帶寬要求；②如果與鄰居協(xié)商的單元格(cell)可用，則6Top層會(huì)給協(xié)商鄰居發(fā)起ADD請(qǐng)求；③接收到6Top ADD請(qǐng)求的相鄰節(jié)點(diǎn)將檢查其6TiSCH調(diào)度，以確定所提出單元格列表的可行性；④鄰居節(jié)點(diǎn)發(fā)送一個(gè)6Top的ADD響應(yīng)(包含一個(gè)建議的單元格列表)。圖1為6TiSCH調(diào)度模型。

圖1 節(jié)點(diǎn)調(diào)度模型

6TiSCH機(jī)制有兩個(gè)特點(diǎn)：所有節(jié)點(diǎn)都是同步的；使用信道跳變。前者使數(shù)據(jù)傳輸更有效率并減少占用時(shí)間，后者使數(shù)據(jù)傳輸更加可靠。許多分布式6TiSCH調(diào)度算法只依賴于基本的6Top隨機(jī)單元格選擇。OTF實(shí)現(xiàn)了帶寬預(yù)留機(jī)制，該機(jī)制將節(jié)點(diǎn)發(fā)送的流量與其每個(gè)鄰居以及相應(yīng)被調(diào)度的單元格進(jìn)行比較，高于/低于某個(gè)閾值，觸發(fā)協(xié)商添加/刪除單元格，由此產(chǎn)生的單元格時(shí)間表不是無(wú)沖突的，如圖2所示, D->C、F->G發(fā)生沖突。

圖2 節(jié)點(diǎn)數(shù)據(jù)轉(zhuǎn)發(fā)

2 建議機(jī)制

本文目的是對(duì)分布式調(diào)度算法進(jìn)行補(bǔ)充，首要目標(biāo)是合理分配中繼節(jié)點(diǎn)流量，實(shí)現(xiàn)負(fù)載均衡，其次是減少數(shù)據(jù)沖突。在無(wú)線傳感網(wǎng)絡(luò)中，節(jié)點(diǎn)大多數(shù)情況下都由電池供電，提升網(wǎng)絡(luò)的整體壽命顯得尤為重要。圖1 中，C作為D和E的中繼節(jié)點(diǎn)，如果沒(méi)有相應(yīng)的分流措施，C節(jié)點(diǎn)的能量消耗必然高于邊界節(jié)點(diǎn)，將導(dǎo)致網(wǎng)絡(luò)的整體壽命縮短，嚴(yán)重影響網(wǎng)絡(luò)性能。此時(shí)，協(xié)商導(dǎo)致D-C、F-G的情況在相同時(shí)隙發(fā)生，而當(dāng)兩個(gè)數(shù)據(jù)同時(shí)被轉(zhuǎn)發(fā)時(shí)，會(huì)產(chǎn)生沖突。如果D能意識(shí)到F-G之間的協(xié)商，或者F能提前知道D-C之間協(xié)商的時(shí)間表，就可以有效避免沖突，提升網(wǎng)絡(luò)可靠性。

2.1 負(fù)載均衡機(jī)制

對(duì)于中繼節(jié)點(diǎn)流量轉(zhuǎn)發(fā)情況，可以通過(guò)6Top調(diào)度發(fā)送數(shù)據(jù)的節(jié)點(diǎn)與鄰居進(jìn)行協(xié)商，當(dāng)鄰居節(jié)點(diǎn)一直處于信息轉(zhuǎn)發(fā)狀態(tài)(單元格數(shù)量一直比較多)而其它鄰居無(wú)數(shù)據(jù)可發(fā)時(shí)，發(fā)送數(shù)據(jù)的節(jié)點(diǎn)就可以通過(guò)協(xié)商平衡流量轉(zhuǎn)發(fā)。并且對(duì)于一些優(yōu)先級(jí)低、實(shí)時(shí)性要求不嚴(yán)格的數(shù)據(jù)，可以通過(guò)犧牲時(shí)延(尋找路徑跳數(shù)較多、數(shù)據(jù)流較少的節(jié)點(diǎn))分散流量，提升網(wǎng)絡(luò)的整體性能。同時(shí)，遇到子節(jié)點(diǎn)或者鄰居消失的突發(fā)情況，通過(guò)6Top子層調(diào)度及時(shí)清理與之有關(guān)的單元格，不再轉(zhuǎn)發(fā)其數(shù)據(jù)，實(shí)現(xiàn)減少能耗的目標(biāo)。本文通過(guò)與鄰居協(xié)商實(shí)現(xiàn)適當(dāng)?shù)牧髁糠峙?，延長(zhǎng)網(wǎng)絡(luò)的整體壽命，使用一個(gè)統(tǒng)計(jì)計(jì)數(shù)的方法實(shí)現(xiàn)(在優(yōu)化二進(jìn)制概率轉(zhuǎn)發(fā)模型中加入計(jì)數(shù)器)。算法如下：

隨機(jī)數(shù)X∈(0，1)，

M為單個(gè)節(jié)點(diǎn)內(nèi)存單元存儲(chǔ)消息的數(shù)據(jù)量，隨著數(shù)據(jù)被轉(zhuǎn)發(fā)會(huì)遞減。

初始化，X，count=0，單元格M>0，

{ while(M≠0)

{ 轉(zhuǎn)發(fā)到B; count++; M——}

else

{ 轉(zhuǎn)發(fā)到C ; count- -; M——}

}

}

2.2 共享信元機(jī)制

6TiSCH定義了6Top協(xié)議，它允許鄰居節(jié)點(diǎn)彼此直接協(xié)商以在本地修改其通信時(shí)間表。然而，節(jié)點(diǎn)使用分布式調(diào)度并發(fā)執(zhí)行數(shù)據(jù)傳輸，并沒(méi)有考慮鄰居的鄰居以相同信道和時(shí)間表發(fā)送數(shù)據(jù)，因此傳輸數(shù)據(jù)會(huì)發(fā)生沖突。本文機(jī)制是節(jié)點(diǎn)時(shí)間表隨著與鄰居的協(xié)商而更新，通過(guò)共享信元廣播給那些可以收到數(shù)據(jù)而不是鄰居的節(jié)點(diǎn)，這些節(jié)點(diǎn)通過(guò)共享信元和OTF調(diào)度，預(yù)先知道協(xié)商的時(shí)間表、信道，通過(guò)6Top調(diào)度避免分配被使用的單元格，可以有效減少?zèng)_突。由圖1可知，6TiSCH網(wǎng)絡(luò)有兩種信元：一種專用信元，用于鄰居之間的協(xié)商和數(shù)據(jù)轉(zhuǎn)發(fā)；一種共享信元，用于接收廣播或者特殊流量。利用共享信元的特點(diǎn)，接收那些不是鄰居但會(huì)產(chǎn)生沖突的節(jié)點(diǎn)時(shí)序分配消息，并且通過(guò)內(nèi)部緩存機(jī)制，在沖突發(fā)生時(shí)進(jìn)行數(shù)據(jù)重傳，提升網(wǎng)絡(luò)可靠性。當(dāng)發(fā)生數(shù)據(jù)沖突時(shí)，R(接收數(shù)據(jù))節(jié)點(diǎn)可以快速為突發(fā)流量生成相應(yīng)時(shí)序，同時(shí)通過(guò)與鄰居協(xié)商啟用碰撞退避算法更新單元格的接收時(shí)序，重新接收T(發(fā)送節(jié)點(diǎn))的數(shù)據(jù)。碰撞退避次數(shù)K值的選取與協(xié)商有關(guān)，K值使用6Top事務(wù)概率模型計(jì)算,是單元格的大小。假設(shè)鄰居成功接收事務(wù)的概率是P,并且成功接收到的傳輸量Y遵循B(K,P)分布。

Y～B(K，P)P0=P(Y≥1)=1-(1-P)K

(1)

(2)

通過(guò)模擬示例拓?fù)洌疚囊呀?jīng)計(jì)算了每個(gè)節(jié)點(diǎn)鄰居的分組傳遞比(PDR)平均值。為了保證建議合理，采取較低的PDR值(P=0.6),根據(jù)方程，得到表1的結(jié)果。

表1 模擬結(jié)果

3 6TiSCH模擬器

6TiSCH模擬器是一個(gè)用Python編寫的開源離散事件模擬器，它實(shí)現(xiàn)了6TiSCH體系結(jié)構(gòu)文檔中定義的標(biāo)準(zhǔn)和協(xié)議。圖3總結(jié)了模擬器使用的一組參數(shù)。每個(gè)無(wú)線鏈路都與一個(gè)數(shù)據(jù)包傳輸率(PDR，一個(gè)介于0～1之間的數(shù)字)相關(guān)聯(lián)。當(dāng)一個(gè)傳感器節(jié)點(diǎn)發(fā)送數(shù)據(jù)時(shí)，連接到鏈路的PDR被用來(lái)確定鄰居是否接收到該分組。PDR根據(jù)每個(gè)鏈路的無(wú)線電信號(hào)強(qiáng)度指示器(RSSI)計(jì)算，由無(wú)線電傳播模型根據(jù)兩個(gè)傳感器微粒之間的距離確定，在仿真運(yùn)行期間恒定。如果不同傳感器在相同時(shí)隙以相同的頻率傳輸，則包沖突，圖4中黑色小方格即為沖突數(shù)據(jù)。在這種情況下，接收器將每個(gè)沖突分組的RSSI轉(zhuǎn)換為映射到PDR的信號(hào)與干擾加噪聲比(SINR)，鏈路的PDR作為沖突分組的干擾函數(shù)被降低。圖5所示為OTF的調(diào)度機(jī)制。

圖3 模擬器參數(shù)

圖4 節(jié)點(diǎn)運(yùn)行模擬

圖5 OTF調(diào)度機(jī)制

4 模擬器優(yōu)化結(jié)果

4.1 網(wǎng)絡(luò)整體壽命延長(zhǎng)

在6TiSCH網(wǎng)絡(luò)中，由于通信發(fā)生在一個(gè)時(shí)隙內(nèi)的特定時(shí)間，所以發(fā)送節(jié)點(diǎn)確切知道何時(shí)發(fā)送數(shù)據(jù)。發(fā)送者與接收者節(jié)點(diǎn)時(shí)間完全同步，接收者節(jié)點(diǎn)將在發(fā)送者開始發(fā)送的瞬間開啟無(wú)線電，其它時(shí)間則處于睡眠待機(jī)狀態(tài)，以節(jié)省能耗。但是，OTF調(diào)度中給出的SF函數(shù)并沒(méi)有明確指出使用什么方法。本文提出分配流量轉(zhuǎn)發(fā)策略，避免網(wǎng)絡(luò)中出現(xiàn)中繼節(jié)點(diǎn)流量過(guò)大而鄰居沒(méi)有數(shù)據(jù)可傳的情況。模擬圖1網(wǎng)絡(luò)結(jié)構(gòu)，如圖6所示，實(shí)驗(yàn)?zāi)Ｐ驮?TiSCH 模擬器里建立，靜態(tài)調(diào)度已經(jīng)在每個(gè)節(jié)點(diǎn)進(jìn)行預(yù)先配置。本文通過(guò)監(jiān)控一段時(shí)間內(nèi)網(wǎng)絡(luò)中繼節(jié)點(diǎn)的能耗情況和數(shù)據(jù)包分配，以驗(yàn)證網(wǎng)絡(luò)整體壽命延長(zhǎng)。

圖6 實(shí)驗(yàn)?zāi)Ｐ?/p>

需要注意的是，睡眠狀態(tài)沒(méi)有能耗。已經(jīng)考慮預(yù)期的信道誤差，可以忽略不計(jì)。圖7給出未優(yōu)化兩個(gè)中繼節(jié)點(diǎn)轉(zhuǎn)發(fā)數(shù)據(jù)包的數(shù)量對(duì)比，圖8給出優(yōu)化以后數(shù)據(jù)包的對(duì)比(總量1 000數(shù)據(jù)包)，兩個(gè)曲線轉(zhuǎn)發(fā)數(shù)據(jù)包的數(shù)量差別不大，說(shuō)明優(yōu)化可靠。

圖7 轉(zhuǎn)發(fā)數(shù)據(jù)包

圖8 優(yōu)化轉(zhuǎn)發(fā)數(shù)據(jù)包

4.2 沖突優(yōu)化

首先，比較OTF的性能，在沒(méi)有優(yōu)化網(wǎng)絡(luò)沖突的情況下，OTF曲線代表原始OTF協(xié)議下的沖突，通過(guò)跟蹤PDR檢查傳輸有問(wèn)題的數(shù)據(jù)幀(見(jiàn)圖9)。其中節(jié)點(diǎn)只避免了與鄰居保留單元的沖突，P曲線對(duì)應(yīng)使用共享數(shù)據(jù)單元檢查沖突的機(jī)制，模擬運(yùn)行1次，運(yùn)行1 000個(gè)周期。仿真開始時(shí)，碰撞相對(duì)較多，是因?yàn)樵诰W(wǎng)絡(luò)初始化階段，RPL創(chuàng)建DODAG期間，所有節(jié)點(diǎn)通過(guò)在共享單元中發(fā)送6個(gè)頂部消息以請(qǐng)求專用單元。共享單元格中的沖突能夠在調(diào)度第一個(gè)專用單元格之前由CSMA/CA逐步解決[14-15]。隨著網(wǎng)絡(luò)穩(wěn)定，碰撞信元的數(shù)目也趨于穩(wěn)定。從圖9中也可以看出，雖然該方法減少了碰撞，但并不能消除碰撞，而且在某些時(shí)候會(huì)增加碰撞。可能原因有：①網(wǎng)絡(luò)狀態(tài)不穩(wěn)定，共享信元被占用；②數(shù)據(jù)量太大，緩存不夠；③突發(fā)節(jié)點(diǎn)比較多。

圖9 碰撞模型

5 結(jié)語(yǔ)

本文討論了提高網(wǎng)絡(luò)整體性能與非鄰居之間沖突的問(wèn)題，解釋了沖突的來(lái)源、OTF調(diào)度存在的問(wèn)題，并提出解決方案。首先，本文首要目標(biāo)是增加網(wǎng)絡(luò)的整體壽命而不是減小節(jié)點(diǎn)能耗，延長(zhǎng)網(wǎng)絡(luò)整體壽命也是無(wú)線傳感網(wǎng)比較關(guān)注的問(wèn)題，通過(guò)流量分流減小中繼節(jié)點(diǎn)的傳輸壓力，一定程度上延長(zhǎng)了網(wǎng)絡(luò)的整體壽命。其次，減少?zèng)_突是利用6TiSCH網(wǎng)絡(luò)共享信元特點(diǎn)實(shí)現(xiàn)的。該方法雖然增加了共享信元的開銷，但是減少了專用信元的碰撞，不影響網(wǎng)絡(luò)整體性能。模擬結(jié)果顯示，碰撞次數(shù)明顯減少。