6TiSCH分布式網絡調度

葉小林

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

0 引言

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

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

1 6TiSCH調度機制

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

圖1 節(jié)點調度模型

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

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

2 建議機制

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

2.1 負載均衡機制

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

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

M為單個節(jié)點內存單元存儲消息的數(shù)據(jù)量，隨著數(shù)據(jù)被轉發(fā)會遞減。

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

{ while(M≠0)

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

else

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

}

}

2.2 共享信元機制

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

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

(1)

(2)

通過模擬示例拓撲，本文已經計算了每個節(jié)點鄰居的分組傳遞比(PDR)平均值。為了保證建議合理，采取較低的PDR值(P=0.6),根據(jù)方程，得到表1的結果。

表1 模擬結果

3 6TiSCH模擬器

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

圖3 模擬器參數(shù)

圖4 節(jié)點運行模擬

圖5 OTF調度機制

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

4.1 網絡整體壽命延長

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

圖6 實驗模型

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

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

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

4.2 沖突優(yōu)化

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

圖9 碰撞模型

5 結語

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