一種用于工業(yè)無線傳感器網絡的動態(tài)調度方法

張本宏,　邱　睿,　黃琳琳

(1.合肥工業(yè)大學 計算機與信息學院,安徽 合肥　230009; 2.合肥工業(yè)大學 安全關鍵工業(yè)測控技術教育部工程研究中心,安徽 合肥　230009)

?

一種用于工業(yè)無線傳感器網絡的動態(tài)調度方法

張本宏1,2,邱睿1,黃琳琳1

(1.合肥工業(yè)大學 計算機與信息學院,安徽 合肥230009; 2.合肥工業(yè)大學 安全關鍵工業(yè)測控技術教育部工程研究中心,安徽 合肥230009)

摘要:傳輸調度是提高無線網絡通信性能的重要手段，針對工業(yè)無線傳感器網絡,文章提出一種基于距離矩陣的動態(tài)調度方法。根據網絡的拓撲結構建立初始時隙分配計劃以及距離矩陣,構建時隙分配表并確定節(jié)點的發(fā)送和接收時隙。該方法既考慮了網絡拓撲結構的影響,又考慮了節(jié)點數據產生周期的影響。仿真結果表明,該方法能顯著降低網絡的平均發(fā)送時間,提高數據傳輸的保真度。

關鍵詞:工業(yè)無線傳感器網絡;確定性;調度方法;時隙分配;距離矩陣

無線網絡因其布線簡單、安裝維護方便,逐漸在工業(yè)現場得到應用[1-3]。與無線傳感器網絡相比,應用于工業(yè)現場的工業(yè)無線傳感器網絡(Industrial Wireless Sensor Networks，IWSNs)對數據通信的確定性和可靠性要求更高[4],因此,對IWSNs的通信進行合理調度,確保數據傳輸過程中的確定性和可靠性,顯得尤為重要。

無線通信的調度方法按照介質訪問控制方式主要分為基于競爭、基于固定時隙分配和兩者相結合3種[4-5]。由于基于競爭的方法,可能在多個節(jié)點同時發(fā)送數據時產生碰撞,難以保證時延的確定性,因此在工業(yè)現場,通常采用基于固定時隙分配的方法[5]。目前,眾多研究者針對不同的應用和不同的優(yōu)化目標,對基于固定時隙分配的調度方法進行了研究。文獻[6-7]針對多跳多基站無線網絡環(huán)境,設計了一種基于干擾管理的高容量跨層優(yōu)化策略,通過迭代方式反復求取更優(yōu)的鏈路分配和路由,但以最大化整個網絡的吞吐量為目標;文獻[8]針對無線傳感器/執(zhí)行器網絡,基于混合模擬退火的微粒群算法,提出了一種動態(tài)調度方法,但主要考慮的是能量均衡因素;文獻[9-10]針對周期性的查詢應用,設計了一種查詢調度方法RTQS(real-time query scheduling),但未考慮節(jié)點數據產生周期不同的影響;文獻[4,11]對符合WIA-PA標準的工業(yè)無線網絡的調度方法和路由選擇進行研究,但未給出各個節(jié)點發(fā)送時隙的分配機理。

本文在上述文獻的基礎上,針對IWSNs的應用,提出一種基于距離矩陣的動態(tài)調度方法,在為節(jié)點進行時隙分配時,既考慮了網絡拓撲結構的影響,又考慮了節(jié)點數據產生周期的不同,可滿足IWSNs對數據傳輸過程中數據可靠性和時延確定性的要求。

1問題描述

IWSNs由工作節(jié)點、路由節(jié)點、匯聚節(jié)點和管理節(jié)點組成。工作節(jié)點周期性產生數據,路由節(jié)點既可以周期性產生數據,又具有路由和信息轉發(fā)功能。圖1所示為一種示例IWSNs的拓撲結構,其中a為匯聚節(jié)點,葉子節(jié)點為工作節(jié)點,其他節(jié)點為路由節(jié)點。與傳統的無線傳感器網絡相比,工作節(jié)點或路由節(jié)點在數據產生以后,必須在一定時間內發(fā)送到匯聚節(jié)點。

圖1　網絡拓撲圖

本文對IWSNs調度方法的研究,主要基于以下假設:

(1) 節(jié)點間任何數據的一次發(fā)送,均在一個時隙內發(fā)送完畢。

(2) 所有數據的產生均具有周期性。

(3) 所有節(jié)點對網絡的全局信息包括節(jié)點位置、數據產生周期均已知。

2基于距離矩陣的動態(tài)調度方法

基于固定時隙分配的調度方法,本質上是為每個節(jié)點合理安排發(fā)送時隙,由于時隙調度是NP難問題,通常采用啟發(fā)式搜索方法[12]。本文的調度方法也采用啟發(fā)式搜索方法,其步驟如下:

(1) 根據網絡的拓撲結構和沖突情況,建立時隙初始分配計劃。

(2) 為每個數據發(fā)送產生計劃實例,建立距離矩陣。

(3) 建立節(jié)點時隙分配表,確定發(fā)送和接收時隙。

2.1建立初始時隙分配計劃

初始時隙分配計劃是根據網絡拓撲產生的有序時隙序列,每個時隙中包含了若干互不沖突的傳輸鏈路集合,將初始時隙分配計劃記為S={s1,s2,…,sL},si表示計劃中的不同時隙,L為初始時隙分配計劃的長度。

在構造初始時隙分配計劃時,將IWSNs視為層次結構,維護completed與eligible 2個集合,completed集合包含已分配了時隙的節(jié)點,eligible集合包含了completed集合目前可達的待分配節(jié)點,但eligible集合中的節(jié)點本身不屬于completed集合。不斷選擇eligible集合中優(yōu)先級最高的節(jié)點,為其分配時隙,將節(jié)點移動到completed集合,再將此節(jié)點的孩子節(jié)點加入eligible集合。

表1　示例網絡的初始時隙分配計劃

2.2建立距離矩陣

初始時隙分配計劃建立后,如果每個節(jié)點按照計劃中的時隙循環(huán)發(fā)送數據,在數據發(fā)送時不產生沖突,但顯然該發(fā)送方式并發(fā)效率較低。例如在時隙1,只有節(jié)點o發(fā)送數據,而實際上此時節(jié)點x、w等均可同時發(fā)送。為了提高發(fā)送效率,需進一步提高數據發(fā)送的并發(fā)性。為此,引入定義1～定義4:

定義1初始時隙分配計劃的每次執(zhí)行稱為計劃實例。

初始時隙分配計劃的每次執(zhí)行并不一定從時隙1開始,1個計劃實例可能包括1個或多個數據的一次完整發(fā)送。例如,對于圖1的示例網絡,如果在某個時隙,只有節(jié)點y有數據發(fā)送,則產生新實例時,該實例從時隙3開始,也即該實例只包括從時隙3到時隙7的5個時隙。

對于不同的實例,如果在發(fā)送時間上存在重疊,就可以提高發(fā)送效率。因此最大限度地提高時隙的重疊數,即減小新實例和正在執(zhí)行實例的相隔時間是提高發(fā)送效率的關鍵。由于不同實例的時隙間可能存在沖突,不能隨意地選擇新實例開始時間,而必須滿足一定條件。

定義2如果計劃實例的si與sj中所有的鏈路都是無沖突的,則稱時隙i與時隙j可以并發(fā)執(zhí)行。

定義3如果新實例與當前實例未執(zhí)行的部分重疊的時隙都是可以并發(fā)執(zhí)行的,則稱這2個實例能夠并發(fā)執(zhí)行。

定義4新實例與當前實例未執(zhí)行的部分能夠并發(fā)執(zhí)行的最小時隙間隔,稱為實例距離。

距離矩陣就是用來表示實例距離的矩陣。對于長度為L的初始時隙分配計劃,當2個實例間的開始時間間隔大于L時不會產生沖突。因此對于長度為L的初始時隙分配計劃,最多有L個時隙實例沖突,因此其距離矩陣可用L×L的三角矩陣D表示,元素Di,j表示當前計劃實例運行到時隙i時,從j時隙開始的新實例應延遲執(zhí)行的時隙數。

對于對角線以下區(qū)域各值,求解步驟如下:

(1) 假設新實例可與當前實例同時開始。

(2) 檢查新實例與當前實例能否并發(fā)執(zhí)行,如果可以并發(fā)執(zhí)行,則當前的延遲執(zhí)行時隙數即為所求；否則,將新實例延遲一個時隙,再次執(zhí)行步驟(2)。

由于從較晚相對時隙開始的新實例能夠合并到從較早相對時隙開始的已有實例中,在距離矩陣中對角線及對角線以上區(qū)域均為0。

由圖1示例網絡計算得出的距離矩陣為:

2.3確定發(fā)送和接收時隙

網絡中各個節(jié)點根據初始時隙分配計劃與距離矩陣,動態(tài)產生時隙分配表,用于決定節(jié)點的數據發(fā)送和接收時隙。

時隙分配表在邏輯上是一種循環(huán)隊列,每個節(jié)點均存在一張時隙分配表。隊列的每個元素表示在一個相對時隙內節(jié)點處于的狀態(tài),0表示發(fā)送狀態(tài),1表示接收狀態(tài),其他值表示空閑狀態(tài),每個節(jié)點使用一個時隙指針指示當前所處的時隙。

為了產生時隙分配表,節(jié)點維護一個就緒計劃實例隊列ready,用于存儲所有已經安排好發(fā)送時隙的計劃實例。節(jié)點在每個時隙到來之前,嘗試將在此時隙開始的數據發(fā)送任務加入已有實例中。如果實例隊列中存在這樣一個實例,其當前所處的時隙早于或等于數據的源節(jié)點在初始時隙分配計劃中的時隙,則該數據能夠加入這個實例。如果有多個這樣的實例,選擇最早開始的一個。如果不存在這樣的實例,則創(chuàng)建一個新實例,再將數據發(fā)送任務加入此實例。

對于一個新實例,需要確定它的發(fā)送時間,以便更新時隙分配表。發(fā)送時間可根據距離矩陣計算確定,分配流程如圖2所示,其中s表示新實例的開始時隙數,i表示就緒計劃實例隊列中的實例,curSlot(i)表示實例i的當前相對時隙。

考慮到距離矩陣反映的是單個當前實例與新實例的計劃距離,而非所有當前實例與新實例的計劃距離,將具體求解步驟表述如下:

(1) 假設新實例的開始時隙數等于當前時隙數。

(2) 計算就緒計劃實例隊列中,每一個當前實例未執(zhí)行的部分與新實例的計劃距離,并選出其中的最大值dmax。

(3) 如果dmax≠0,將新實例的開始延遲dmax個時隙,轉到步驟(2)；否則新實例可以與所有當前實例并發(fā)執(zhí)行,求解結束。

圖2　時隙分配流程圖

數據加入實例后,即表示數據的發(fā)送時隙已被確定,數據傳輸到匯聚需經過的每個節(jié)點修改各自的時隙分配表,在數據對應的實際工作時隙進行發(fā)送或接收。時隙分配表總是丟棄已經逝去的時隙項,而一個新實例的開始時間間隔不會大于L,也即時隙分配表的長度不會超過2L。

3算法仿真

為了驗證本算法的性能,在網絡仿真器NS3上進行仿真,并與文獻[10]的RTQS方法進行性能比較。在仿真場景中,網絡帶寬為2 Mb/s,網絡中數據的長度被設置為固定的200 Bytes(包含幀頭),時間片長度為10 ms。

3.1不同網絡規(guī)模下的性能比較

在本次比較中,網絡中的數據數量與節(jié)點數呈正相關,數據的產生周期與截止期相同,并被隨機劃分為3種長度,比值為1∶1.2∶1.4,基準長度與初始時隙分配計劃長度相等。

在不同的網絡規(guī)模中本文方法與RTQS的響應時間以及保真度情況如圖3所示。在本文中,響應時間指數據從產生到被基站接收所流逝的時間,而數據保真度是指數據能夠在截止期前送到基站的比例。

由于RTQS中并未考慮到數據發(fā)送任務于不同周期產生的情況,將RTQS的查詢頻率控制在不同的值上進行了2次仿真,2種頻率分別是網絡中周期最快任務的產生頻率以及最慢任務的產生頻率。

在圖3中可以看出,高頻率RTQS的響應時間低于低頻率RTQS的響應時間,而數據保真度則相反,高頻率RTQS的數據保真度更高。

本文算法與2種情況的RTQS相比,平均響應時間更低,而數據保真度更高。在網絡規(guī)模較小時,由于調度計劃長度小,兩者響應時間差異不大,但是當網絡規(guī)模逐步變大時,由于調度計劃長度隨之增大,而RTQS沒有考慮到任務產生周期的不同,只能在統一的時間發(fā)出一次完全的查詢,造成周期與查詢間隔不一致的任務響應時間惡化,進一步導致了數據保真度的降低。

圖3　不同網絡規(guī)模下的性能比較

3.2不同查詢頻率下的性能比較

在本次比較中,網絡中節(jié)點數量被固定為40個,每次仿真中網絡拓撲是一致的,數據發(fā)送任務仍然被劃分為3種,通過改變任務的基準周期長度來改變網絡的查詢頻率。不同查詢頻率下本文方法與RTQS的響應時間以及保真度情況如圖4所示。

在查詢頻率較低時,本文算法響應時間低于RTQS,且數據保真度更好,隨著查詢頻率升高,本文算法由于新實例產生過于頻繁,越來越多的實例從初始時隙分配計劃的第1步開始,因此2種方法表現接近一致。

圖4　不同查詢頻率下的性能比較

4結束語

本文研究了在工業(yè)無線傳感器網絡中基于距離矩陣的動態(tài)調度方法。根據工業(yè)無線傳感器網絡的特點,設計了初始時隙分配計劃與距離矩陣,以此為依據進行動態(tài)調度。通過仿真證明了本文提出的調度方法可以在保證網絡可靠性的前提下,合理分配時隙,降低網絡的平均響應時間,并提高數據保真度。

[參考文獻]

[1]Gungor V C，Hancke G P.Industrial wireless sensor networks:challenges，design principles，and technical approaches[J].IEEE Transactions on Industrial Electronics,2009，56(10):4258-4265.

[2]楊成,馮琳，魏振春,等.基于數據插值和權重指數的礦井機車無線定位方法[J].合肥工業(yè)大學學報:自然科學版，2013，36(11):1331-1334.

[3]Bal M.An industrial Wireless Sensor Networks framework for production monitoring[C]//2014 IEEE 23rd International Symposium on Industrial Electronics (ISIE).IEEE，2014:1442-1447.

[4]王平，劉其琛，王恒，等.一種適用于 ISA100.11a 工業(yè)無線網絡的通信調度方法[J].儀器儀表學報，2011，32(5):1189-1195.

[5]張曉玲，梁煒，于海斌，等.無線傳感器網絡傳輸調度方法綜述[J].通信學報,2012,33(5):143-157.

[6]石雷，韓江洪，石怡，等.多包接收無線 Mesh 網絡的跨層優(yōu)化[J].應用科學學報，2012，30(3):227-233.

[7]石雷，韓江洪，石怡，等.無線多跳網絡下基于干擾管理的高容量跨層優(yōu)化策略[J].通信學報，2014，35(12):89-97.

[8]易軍，石為人，唐云建，等.無線傳感器/執(zhí)行器網絡任務動態(tài)調度策略[J].電子學報，2010，38(6):1239-1244.

[9]Chipara O，Lu C，Stankovic J，et al.Dynamic conflict-free transmission scheduling for sensor network queries[J].IEEE Transactions on Mobile Computing，2011，10(5):734-748.

[10]Chipara O，Lu C，Roman G C.Real-time query scheduling for wireless sensor networks [J].IEEE Transactions on Computers，2013，62(9):1850-1865.

[11]王恒，李敏，劉其琛，等.一種基于確定性調度的工業(yè)無線網絡路由算法[J].儀器儀表學報，2011，32(9):1921-1928.

[12]毛劍琳，吳智銘.無線傳感器網絡 TDMA 調度的能量-時延 Pareto 優(yōu)化[J].控制與決策，2007，22(9):967-971.

(責任編輯馬國鋒)

A dynamic scheduling method for Industrial Wireless Sensor Networks

ZHANG Ben-hong1，2,QIU Rui1,HUANG Lin-lin1

(1.School of Computer and Information， Hefei University of Technology， Hefei 230009， China; 2.Engineering Research Center of Safety Critical Industrial Measurement and Control Technology of Ministry of Education， Hefei University of Technology， Hefei 230009， China)

Abstract:Transmission scheduling is an important approach to improve wireless network performance. In this paper, a distance matrix based dynamic scheduling method for Industrial Wireless Sensor Networks(IWSNs) is presented. In the method, the initial slot allocation plan and the distance matrix are constructed according to the network topology， the slot allocation table is established，and then the transmitting and receiving slots of nodes are determined. The method not only takes into account the impact of network topology，but also considers the impact of data generation cycle of nodes. The simulation results show that the method can dramatically decrease the average response time of the network and improve data fidelity.

Key words:Industrial Wireless Sensor Networks(IWSNs); determinism; scheduling method; slot allocation; distance matrix

中圖分類號:TP393.02

文獻標識碼：A

文章編號：1003-5060(2016)03-0333-05

doi:10.3969/j.issn.1003-5060.2016.03.009

作者簡介：張本宏(1972-),男,安徽無為人,博士,合肥工業(yè)大學副教授,碩士生導師.

基金項目：國家自然科學基金資助項目(61370088);國家國際科技合作專項資助項目(2014DFB10060)和安徽省自然科學基金資助項目(1308085MF100)

收稿日期：2015-01-16；修回日期：2015-03-24