層次型軟件定義無線傳感器網(wǎng)絡(luò)資源調(diào)度策略

甄 巖，趙 虎

(1.重慶郵電大學(xué) 通信與信息工程學(xué)院，重慶 400065；2．重慶高校市級光通信與網(wǎng)絡(luò)重點實驗室，重慶 400065；3.泛在感知與互聯(lián)重慶市重點實驗室，重慶 400065；4.國網(wǎng)信息通信產(chǎn)業(yè)集團有限公司，北京 100031)

無線傳感器網(wǎng)絡(luò)(Wireless Sensor Networks，WSN)由一系列能夠監(jiān)測物理和環(huán)境因素的微型傳感器節(jié)點組成，廣泛應(yīng)用于智能電網(wǎng)、目標(biāo)跟蹤和環(huán)境監(jiān)測等領(lǐng)域[1]。但是，針對特定任務(wù)部署的傳統(tǒng)無線傳感網(wǎng)存在著網(wǎng)絡(luò)資源利用不充分以及節(jié)點能耗不均衡的問題，其主要原因在于不同供應(yīng)商的多個傳感器網(wǎng)絡(luò)獨立部署在同一監(jiān)測區(qū)域中，相互之間資源無法共享，使得有限的節(jié)點資源得不到有效復(fù)用，從而極大地降低了網(wǎng)絡(luò)壽命。此外，傳統(tǒng)無線傳感器網(wǎng)絡(luò)對專有服務(wù)過度依賴，缺乏實現(xiàn)即時更改的靈活性，面對網(wǎng)絡(luò)拓撲的動態(tài)變化，無法及時響應(yīng)，并采取有效措施。因此，如何在節(jié)點資源有限，且網(wǎng)絡(luò)動態(tài)變化的情況下，通過靈活高效的節(jié)點及網(wǎng)絡(luò)資源調(diào)度策略來優(yōu)化網(wǎng)絡(luò)性能具有重要研究意義。

上述問題在傳統(tǒng)無線傳感網(wǎng)架構(gòu)下很難有效解決。但是，通過將軟件定義網(wǎng)絡(luò)(Software Defined Networking，SDN)[2]引入無線傳感網(wǎng)，可實現(xiàn)高效的網(wǎng)絡(luò)資源調(diào)度以及靈活的網(wǎng)絡(luò)管理，成為上述問題行之有效的解決方案之一，并由此產(chǎn)生了軟件定義無線傳感器網(wǎng)絡(luò)(Software-Defined Wireless Sensor Networks，SDWSN)[3]。SDWSN將控制邏輯從傳感器節(jié)點轉(zhuǎn)移到邏輯集中的主節(jié)點(控制服務(wù)器)，實現(xiàn)了控制層和數(shù)據(jù)層的解耦，并使普通節(jié)點僅具有數(shù)據(jù)收集和轉(zhuǎn)發(fā)功能，提高其工作效率，并降低能耗；而主節(jié)點則具備全局網(wǎng)絡(luò)視圖，可根據(jù)不同任務(wù)請求靈活調(diào)度網(wǎng)絡(luò)資源，選擇激活最少的底層節(jié)點來同時執(zhí)行多個任務(wù)，解決傳統(tǒng)無線傳感器網(wǎng)絡(luò)資源調(diào)度不合理、節(jié)點能量效率低下等問題。此外，當(dāng)網(wǎng)絡(luò)動態(tài)事件(節(jié)點加入、離開)發(fā)生時，主節(jié)點可依據(jù)全局網(wǎng)絡(luò)視圖及時獲知拓撲變化，然后通過簇內(nèi)資源調(diào)度激活或關(guān)閉節(jié)點，保證監(jiān)測質(zhì)量，并降低能耗。

目前，國內(nèi)外研究人員針對SDWSN開展了一定程度的探索。文獻[4]提出了一種基于軟件定義網(wǎng)絡(luò)的無線傳感器網(wǎng)絡(luò)框架(SDNSense)，通過軟件定義網(wǎng)絡(luò)將網(wǎng)絡(luò)控制從硬件中分離，以提高網(wǎng)絡(luò)靈活性，并動態(tài)適應(yīng)網(wǎng)絡(luò)變化。在文獻[5]中，作者通過軟件定義網(wǎng)絡(luò)實現(xiàn)無線傳感網(wǎng)的自動重配置，并提出了一種基于自適應(yīng)粒子群優(yōu)化算法的綠色路由算法，以最大限度地延長網(wǎng)絡(luò)壽命。文獻[6]提出了一種用于物聯(lián)網(wǎng)的軟件定義無線傳感器網(wǎng)絡(luò)架構(gòu)(Soft-WSN)，通過軟件定義的控制器實現(xiàn)設(shè)備管理和網(wǎng)絡(luò)管理，以滿足物聯(lián)網(wǎng)應(yīng)用需求。上述文獻主要研究了SDWSN的架構(gòu)設(shè)計及其實現(xiàn)，重點描述了如何通過軟件定義網(wǎng)絡(luò)實現(xiàn)無線傳感器網(wǎng)絡(luò)的解耦。而在SDWSN資源調(diào)度方面，文獻[7]提出了一種基于軟件定義網(wǎng)絡(luò)的無線傳感網(wǎng)睡眠調(diào)度機制，通過控制器執(zhí)行資源調(diào)度算法來決定節(jié)點狀態(tài)，消除了每個周期內(nèi)兩次廣播過程以減少通信能耗。但是，該調(diào)度機制靈活性不足，因為控制器僅在每個周期開始時根據(jù)節(jié)點上傳的信標(biāo)信息來決定其休眠與否，無法根據(jù)網(wǎng)絡(luò)變化實時修改節(jié)點狀態(tài)。文獻[8]在SDWSN中設(shè)計了一種節(jié)能的網(wǎng)絡(luò)資源再調(diào)度策略，通過控制器向節(jié)點載入不同程序來對其功能進行動態(tài)重編程，以高效調(diào)度節(jié)點資源滿足不同任務(wù)需求。但是，在資源調(diào)度過程中，僅考慮了再調(diào)度時的能量消耗，并沒有考慮節(jié)點的可調(diào)度性和內(nèi)存約束等問題。文獻[9]將無線電力傳輸技術(shù)引入到SDWSN中，提出了優(yōu)化的能量發(fā)射器放置機制，以及高能效的網(wǎng)絡(luò)資源調(diào)度策略。但是，當(dāng)節(jié)點能量過低或者網(wǎng)絡(luò)拓撲發(fā)生變化時，需要頻繁地在整個網(wǎng)絡(luò)范圍內(nèi)執(zhí)行能量發(fā)射器調(diào)度機制，不夠靈活，且再調(diào)度時間過長。

針對傳統(tǒng)無線傳感器網(wǎng)絡(luò)資源利用不合理、網(wǎng)絡(luò)僵化不靈活以及現(xiàn)有SDWSN資源調(diào)度機制存在的問題，筆者提出了層次型軟件定義無線傳感網(wǎng)中的資源調(diào)度策略(Resource scheduling Strategy in Hierarchical Software Defined Wireless Sensor Networks，RS-HSDWSN)。首先，通過分簇建立層次型網(wǎng)絡(luò)結(jié)構(gòu)，并將軟件定義網(wǎng)絡(luò)中數(shù)據(jù)層擴展的思想引入，把主節(jié)點部分控制功能下放到位于數(shù)據(jù)層的簇頭中以緩解其控制開銷; 然后，主節(jié)點采用集中調(diào)度的方式，合理利用底層網(wǎng)絡(luò)資源，解決基于特定任務(wù)的無線傳感網(wǎng)因多任務(wù)在網(wǎng)絡(luò)區(qū)域中重復(fù)部署的問題；最后，在聯(lián)合考慮任務(wù)監(jiān)測質(zhì)量和節(jié)點監(jiān)測能力的基礎(chǔ)上，最小化激活節(jié)點數(shù)量以減小網(wǎng)絡(luò)總能耗。此外，當(dāng)網(wǎng)絡(luò)拓撲發(fā)生變化時，選擇在簇頭節(jié)點處采用簇內(nèi)資源調(diào)度以保證任務(wù)監(jiān)測質(zhì)量，并合理降低網(wǎng)絡(luò)能耗。與全局資源調(diào)度相比，簇內(nèi)調(diào)度僅需請求局部網(wǎng)絡(luò)信息，可提高優(yōu)化效率和網(wǎng)絡(luò)靈活性。

1 系統(tǒng)模型

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

將基于OpenFlow的軟件定義網(wǎng)絡(luò)架構(gòu)引入無線傳感器網(wǎng)絡(luò)，結(jié)合分簇及數(shù)據(jù)層擴展的思想，形成層次型的軟件定義無線傳感網(wǎng)結(jié)構(gòu)，其網(wǎng)絡(luò)架構(gòu)如圖1所示。SDWSN中的主節(jié)點對應(yīng)于OpenFlow中的控制服務(wù)器，具有充足的電量和較強的處理能力；還對應(yīng)于數(shù)據(jù)層擴展中的根控制器，用以執(zhí)行需要全局視圖的任務(wù)，如分簇以及全局網(wǎng)絡(luò)資源調(diào)度。SDWSN中的簇頭節(jié)點對應(yīng)于OpenFlow交換機，用于融合并轉(zhuǎn)發(fā)簇內(nèi)節(jié)點監(jiān)測數(shù)據(jù)；簇頭還對應(yīng)于數(shù)據(jù)層擴展中的本地控制器，其作用是緩解主節(jié)點控制開銷，并執(zhí)行無需全局視圖的任務(wù)，如簇內(nèi)資源調(diào)度。SDWSN中的普通節(jié)點僅負責(zé)監(jiān)測，并生成數(shù)據(jù)，然后將數(shù)據(jù)發(fā)送給簇頭節(jié)點。

圖1 SDWSN模型

圖2 節(jié)點和任務(wù)映射關(guān)系(多對多)

筆者提出的層次型SDWSN由一個主節(jié)點和大量軟件定義節(jié)點組成。每個軟件定義節(jié)點都裝備了具有不同監(jiān)測能力的多個傳感器，例如溫度、濕度傳感器等。其中每個子傳感器均能監(jiān)測某個特定任務(wù)中的監(jiān)測目標(biāo)。因此，一個軟件定義節(jié)點能夠同時執(zhí)行多個任務(wù)，如圖2(a)所示。針對監(jiān)測任務(wù)而言，每個任務(wù)都有相應(yīng)的監(jiān)測目標(biāo)集合，而每個目標(biāo)可由一個或多個節(jié)點協(xié)同完成監(jiān)測，如圖2(b)所示。因此，筆者提出的SDWSN網(wǎng)絡(luò)模型能夠處理多任務(wù)并發(fā)問題，而無須在監(jiān)測區(qū)域重復(fù)部署。

在SDWSN中，數(shù)據(jù)層的軟件定義節(jié)點和控制層的控制器之間通過文獻[10]提出的Sensor OpenFlow(SOF)協(xié)議進行通信。為適應(yīng)無線傳感器網(wǎng)絡(luò)特性，需對OpenFlow作必要的修改。在數(shù)據(jù)平面，與以地址為中心的OpenFlow網(wǎng)絡(luò)相反，無線傳感器網(wǎng)絡(luò)通常以數(shù)據(jù)為中心，并采用了不同的尋址方式。所以，在基于軟件定義網(wǎng)絡(luò)的無線傳感器網(wǎng)絡(luò)中，需要重新定義流表以滿足傳感網(wǎng)中特殊尋址方案。

無線傳感器網(wǎng)絡(luò)尋址方案可分為Class-1(緊湊型網(wǎng)絡(luò)唯一尋址)和Class-2(級聯(lián)屬性值對(CAV))。針對Class-1，通過利用OpenFlow可擴展匹配(OXM)來解決，在SOF中引入兩個新的oxm_type來表示Class-1地址：OXM_SOF_SRC(源)和OXM_SOF_DST(目的地)，并在同一個OXM框架下構(gòu)造Class-1流表匹配即可；針對Class-2，通過引入CAV格式來完成流表的重新定義，然后通過添加新的oxm_type，OXM_SOF_CAV，便可創(chuàng)建任意的Class-2流。

在控制平面，需要設(shè)計SOF信道，用于節(jié)點上傳告警和網(wǎng)絡(luò)狀態(tài)信息或者由控制器下達控制指令。在數(shù)據(jù)層重新定義流表的基礎(chǔ)上，SDWSN在控制層設(shè)計SOF信道的優(yōu)勢在于，可以通過直接在無線傳感器網(wǎng)絡(luò)上覆蓋傳輸協(xié)議來提供SOF信道。傳感網(wǎng)中傳輸協(xié)議的設(shè)計已經(jīng)具有十分廣泛的研究成果，在此不再贅述。

在SDWSN中通過SOF信道傳輸?shù)目刂茢?shù)據(jù)包含兩種類型，節(jié)點發(fā)送給控制器的拓撲變化和告警信息(packet-in)，控制器發(fā)送給節(jié)點的激活/休眠指令和流表規(guī)則(packet-out)。這些控制數(shù)據(jù)會占用控制器和底層網(wǎng)絡(luò)資源。為降低資源占用，筆者采取的策略包括：其一，針對packet-in數(shù)據(jù)，根據(jù)Sensor OpenFlow協(xié)議的思想，將目的地地址相同的packet-in數(shù)據(jù)捆綁到流中可有效減少傳輸數(shù)據(jù)量；其二，針對packet-out數(shù)據(jù)，筆者通過數(shù)據(jù)層擴展，由簇頭解決網(wǎng)絡(luò)動態(tài)事件，避免了控制器因網(wǎng)絡(luò)動態(tài)頻繁地產(chǎn)生控制信息。

1.2 能耗模型

以文獻[11]中SDWSN能耗模型為基礎(chǔ)，結(jié)合文獻[12]提出的基于分簇的節(jié)點耗能模型，在層次型軟件定義傳感器網(wǎng)絡(luò)框架下，給出符合本文網(wǎng)絡(luò)模型的能量消耗模型如下：

基于分簇的SDWSN由三部分組成：主節(jié)點、簇頭節(jié)點和普通節(jié)點。主節(jié)點由外部電網(wǎng)供電，因此筆者不討論其能量消耗。簇頭節(jié)點和普通節(jié)點的能耗由通信模塊、處理模塊和監(jiān)測模塊三部分組成。

普通節(jié)點發(fā)送kbit數(shù)據(jù)到距離為d處所消耗的能量由發(fā)射電路損耗和功率放大損耗兩部分構(gòu)成，即

(1)

對于簇頭節(jié)點，融合并發(fā)送kbit數(shù)據(jù)所需的能量消耗為

(2)

其中，EDA表示融合1 bit數(shù)據(jù)的能耗，d代表節(jié)點之間的距離，Eelec表示發(fā)送或接收1 bit數(shù)據(jù)的能耗。εfs和εmp分別表示自由空間和多徑模型中功率放大的能耗，k是發(fā)送數(shù)據(jù)的長度，d0是傳輸距離閾值。

傳感器節(jié)點接收kbit數(shù)據(jù)所消耗的能量為

ERX(k)=kEelec。

(3)

將軟件定義網(wǎng)絡(luò)引入無線傳感器網(wǎng)絡(luò)后，普通節(jié)點的總通信能耗僅包括發(fā)送數(shù)據(jù)部分(ETX)，不再轉(zhuǎn)發(fā)來自其它節(jié)點的數(shù)據(jù)，所以其通信能耗由以下公式表示：

(4)

而簇頭節(jié)點需要負責(zé)接收其成員節(jié)點的數(shù)據(jù)，在完成數(shù)據(jù)融合之后以多跳方式發(fā)送給主節(jié)點。假定在基于分簇的軟件定義無線傳感網(wǎng)中，一個簇由m個節(jié)點組成，那么其通信能耗可表示為

(5)

在處理模塊部分，節(jié)點處理數(shù)據(jù)所需的能量消耗為Ecpu；監(jiān)測模塊部分，傳感器執(zhí)行監(jiān)測操作的能耗為Esen，而通信模塊產(chǎn)生的能量消耗即為上述Ecom。

引入軟件定義網(wǎng)絡(luò)后，普通節(jié)點不再做任何路由決策和數(shù)據(jù)處理，移除了處理模塊部分的能耗(Ecpu)，因此，其總能耗由以下公式表示：

(6)

而簇頭節(jié)點的總能耗則可表示為

(7)

綜上所述，激活的節(jié)點總能量消耗為Etotal，而處于休眠狀態(tài)的節(jié)點僅需維持傳感器的基本能量消耗，定義為Esleep。

2 分簇算法

通過分簇使簇頭節(jié)點保留部分控制功能，緩解主節(jié)點控制開銷的同時保留了傳統(tǒng)無線傳感器網(wǎng)絡(luò)分布式處理的優(yōu)勢。主節(jié)點擁有全局網(wǎng)絡(luò)視圖，因此,分簇操作在主節(jié)點中完成更為合理。選用該分簇算法的原因有三：其一，位于SDWSN控制層的主節(jié)點采用的是集中調(diào)度的方式，所以必須選用集中式分簇，而非分布式分簇算法；其二，算法設(shè)計時，將分簇和資源調(diào)度過程中考慮的因素相匹配，減少了重復(fù)的信息收集以及不必要的操作，從而提高整個網(wǎng)絡(luò)的效率；其三，該算法實現(xiàn)簡單,且考慮分簇因素更為全面。

該算法通過對剩余能量、相對位置和節(jié)點度的綜合分析，選取最合適的節(jié)點充當(dāng)簇頭并建簇。首先引入以下幾個定義：

鄰居節(jié)點：在節(jié)點i廣播半徑Rb內(nèi)的節(jié)點稱為其鄰居節(jié)點，用Ni表示。

節(jié)點度：節(jié)點i鄰居節(jié)點的數(shù)量，用Mi表示，表征選取該節(jié)點作為簇頭時的覆蓋能力。

節(jié)點間相對距離：節(jié)點i接收其廣播半徑內(nèi)的全部節(jié)點的廣播消息，用Sj表示來自于節(jié)點j的廣播信號強度。那么節(jié)點間相對距離Di可由以下公式表示：

(8)

Di越大，表示節(jié)點i與鄰居節(jié)點之間的平均距離越短，意味著它們之間進行通信時具有更小的能耗。

分簇算法可分為消息廣播階段和節(jié)點角色確定階段，詳細過程如下：

消息廣播階段：所有節(jié)點廣播一條HELLO_MSG消息，并根據(jù)接收到的廣播消息計算Ni、Mi以及相對距離Di，然后將上述信息及自身剩余能量打包通過SOF信道發(fā)送給主節(jié)點。

節(jié)點角色確定階段：主節(jié)點根據(jù)接收到的節(jié)點狀態(tài)信息確定簇頭及其成員節(jié)點。具體操作如下：

(1)根據(jù)式(9)計算每個節(jié)點的等待時間ti，然后主節(jié)點開啟計時操作。如果計時到ti時節(jié)點i仍沒有收到來自任何一個簇頭的消息，那么該節(jié)點將作為簇頭，并發(fā)送消息告知其鄰居節(jié)點。ti由以下公式給出：

ti=ηe-wi,

(9)

其中，η是決定網(wǎng)絡(luò)延遲大小的比例因子。wi表征節(jié)點i成為簇頭的概率大小，由節(jié)點度、剩余能量以及節(jié)點間距離決定，并由以下公式給出定義：

(10)

(2)如果節(jié)點i在ti內(nèi)接收到來自某個簇頭的消息，那么該節(jié)點作為成員節(jié)點加入由此簇頭形成的簇。

(3)如果節(jié)點i接收到來自多個簇頭的消息，那么該節(jié)點選擇加入最后發(fā)送消息給這個節(jié)點的簇。因為文中簇頭選擇的方式使得先形成的簇大小大于后形成的簇，所以選擇加入后形成的簇可平衡每個簇的大小。

式(9)和(10)表明，擁有更高節(jié)點度、更多剩余能量，與周圍節(jié)點平均距離更短以及離主節(jié)點更近的節(jié)點，將會具有更短的等待時間ti以及更大的概率成為簇頭。通過上述方式來確保簇頭選擇的合理性，使其具有更好的覆蓋能力和生命周期，同時與周圍節(jié)點和主節(jié)點具有更小的通信能耗。

3 資源調(diào)度策略

筆者提出的資源調(diào)度策略可分為兩個階段。第一階段，分簇完成之后，主節(jié)點根據(jù)同時到達的多個任務(wù)，分析其監(jiān)測質(zhì)量要求，然后通過全局網(wǎng)絡(luò)視圖，獲取節(jié)點當(dāng)前監(jiān)測能力(包括剩余能量、內(nèi)存占用和監(jiān)測速率等)，最后完成整個網(wǎng)絡(luò)范圍內(nèi)的資源調(diào)度，最小化激活節(jié)點數(shù)量來同時完成多個任務(wù)，達到全局最優(yōu)；第二階段，當(dāng)網(wǎng)絡(luò)動態(tài)事件發(fā)生時，通過簇頭節(jié)點激活或關(guān)閉相應(yīng)節(jié)點來實現(xiàn)簇內(nèi)資源調(diào)度，保證監(jiān)測質(zhì)量，并提高優(yōu)化效率，達到局部最優(yōu)。

3.1 全局網(wǎng)絡(luò)資源調(diào)度

實現(xiàn)全局網(wǎng)絡(luò)資源調(diào)度需要考慮的因素有兩方面，對任務(wù)的監(jiān)測質(zhì)量約束和對節(jié)點自身監(jiān)測能力的約束。因為，只有滿足任務(wù)監(jiān)測質(zhì)量要求，才表示該任務(wù)被有效執(zhí)行，這是保證任務(wù)完成度必須考慮的因素之一；此外，SDWSN中的軟件定義節(jié)點除了能量之外，內(nèi)存和監(jiān)測速率等資源都十分有限，所以主節(jié)點必須充分考慮節(jié)點當(dāng)前監(jiān)測能力，通過調(diào)度有限的資源來解決多任務(wù)并發(fā)問題。

3.1.1 任務(wù)監(jiān)測質(zhì)量約束

在無線傳感網(wǎng)中，任務(wù)監(jiān)測質(zhì)量是用戶最關(guān)心的問題，而良好的覆蓋能夠有效提高傳感網(wǎng)的監(jiān)測效果[13]，因此，采用覆蓋率對監(jiān)測質(zhì)量加以量化。一個任務(wù)中存在多個監(jiān)測目標(biāo)，只有傳感器節(jié)點對目標(biāo)的監(jiān)測速率大于最小監(jiān)測率ft，才表示該目標(biāo)被覆蓋。當(dāng)任務(wù)中被覆蓋的目標(biāo)數(shù)達到最小覆蓋率要求(定義為λt)時，表明該任務(wù)的監(jiān)測質(zhì)量得以滿足。

假設(shè)所有節(jié)點以及任務(wù)中的監(jiān)測目標(biāo)隨機分布在網(wǎng)絡(luò)區(qū)域中，只有任務(wù)t(t∈T)中的目標(biāo)g(g∈Gt)在軟件定義節(jié)點s(s∈S)的監(jiān)測范圍內(nèi)時，該目標(biāo)才能夠被節(jié)點s監(jiān)測，兩者關(guān)系如式(11)所示。

(11)

一個軟件定義節(jié)點s能夠監(jiān)測任務(wù)t中的目標(biāo)g，有且僅有滿足：(1)目標(biāo)g在傳感器節(jié)點s的監(jiān)測范圍之內(nèi)，即φs tg=1；(2)任務(wù)t能夠調(diào)度傳感器節(jié)點s。為此，定義了一個二進制變量αs t，表示任務(wù)t能否調(diào)度傳感器節(jié)點s。

(12)

以βs tg表示傳感器節(jié)點s能否監(jiān)測任務(wù)t中的目標(biāo)g，即

βs tg=αs tφs tg, ?s∈S,t∈T,g∈Gt。

(13)

對于任何一個滿足監(jiān)測質(zhì)量要求的監(jiān)測目標(biāo)，必須達到最小監(jiān)測率以保證其獲得有用監(jiān)測信息。傳感器節(jié)點s對任務(wù)t中目標(biāo)g的監(jiān)測速率fs tg首先由βs tg決定：

0≤fs tg≤βs tgf, ?s∈S, ?t∈T, ?g∈Gt。

(14)

上式表明，只有當(dāng)軟件定義節(jié)點s能夠監(jiān)測目標(biāo)g，fs tg才能被分配到一個大于0的值。

(15)

(16)

(17)

為了保證任務(wù)監(jiān)測質(zhì)量，對于某個任務(wù)t，最小覆蓋率要求λt必須被滿足。因此，覆蓋率約束,即對任務(wù)的監(jiān)測質(zhì)量約束可表示如下：

(18)

其中，δt g=1，表示監(jiān)測目標(biāo)g被覆蓋，|Gt|表示任務(wù)t中的監(jiān)測目標(biāo)總數(shù)。

3.1.2 節(jié)點監(jiān)測能力約束

一個軟件定義節(jié)點可能需要同時監(jiān)測多個目標(biāo)。為獲得有用監(jiān)測數(shù)據(jù)，每個任務(wù)中的目標(biāo)均要求節(jié)點能夠為其提供一個確定的監(jiān)測速率fs tg和監(jiān)測持續(xù)時間dt。因此，所有節(jié)點均需要滿足以下可調(diào)度性約束：

(19)

上式是為了保證節(jié)點對多任務(wù)的可調(diào)度性，只有該節(jié)點當(dāng)前對目標(biāo)的監(jiān)測速率和監(jiān)測持續(xù)時間滿足任務(wù)要求，此節(jié)點才能夠被該任務(wù)調(diào)度，用以監(jiān)測這個任務(wù)中的目標(biāo)。

一個軟件定義節(jié)點能夠同時執(zhí)行多個任務(wù)，但只有將相應(yīng)任務(wù)的程序載入到節(jié)點中，該節(jié)點才能夠被激活，并執(zhí)行監(jiān)測操作。不同任務(wù)具有不同程序大小，考慮同構(gòu)的傳感器網(wǎng)絡(luò)，即所有節(jié)點具有相同的存儲能力，并將其歸一化為1.0。因此，當(dāng)一個軟件定義節(jié)點被多個任務(wù)調(diào)度時，其總程序大小不得超過該節(jié)點存儲容量，將其定義為存儲約束，并表示如下：

(20)

其中，αs t表示節(jié)點s能否被任務(wù)t調(diào)度，pt表示執(zhí)行任務(wù)t所需占用的歸一化內(nèi)存大小。

此外，執(zhí)行任務(wù)過程中，必須考慮節(jié)點的剩余能量。能量過低的節(jié)點將不能被激活用以相應(yīng)任務(wù)的執(zhí)行。在部署節(jié)點時設(shè)置閾值，能量高于該閾值的節(jié)點能夠正常執(zhí)行監(jiān)測、處理和通信任務(wù)。因此，節(jié)點的能量約束由以下公式給出：

(21)

3.1.3 資源調(diào)度目標(biāo)及求解

如果某個節(jié)點被至少一個任務(wù)調(diào)度，那么該節(jié)點將被激活以執(zhí)行相應(yīng)監(jiān)測操作。用二進制變量as表示節(jié)點s是否被激活，即

(22)

對于節(jié)點s，如果存在任務(wù)t∈T,使得αs t=1,那么as≡1；對于任意t∈T，都有αs t=0時，則as≡0。

資源調(diào)度的目標(biāo)是在多任務(wù)并發(fā)的情況下，滿足不同任務(wù)的監(jiān)測質(zhì)量要求，并最小化網(wǎng)絡(luò)總能耗，等價于激活最少的節(jié)點同時完成多個任務(wù)。其目標(biāo)函數(shù)及約束條件可表示如下：

(23)

上述問題是一個典型的0-1整數(shù)規(guī)劃問題，其中一個優(yōu)化方案是枚舉所有as可能的組合，通過比較目標(biāo)函數(shù)值來求取最優(yōu)解，這個方法的計算量非常巨大。因此，采用求解0-1整數(shù)規(guī)劃問題最常用的方法——分支定界法來解決SDWSN中軟件定義節(jié)點的激活調(diào)度問題。

算法1運用分支定界法獲得SDWSN中最佳激活調(diào)度方案。

②While 活節(jié)點列表中存在一部分活節(jié)點 do

③選擇一個活節(jié)點k并標(biāo)記

④解決整數(shù)規(guī)劃松弛后的線性規(guī)劃(LP)問題：

定義激活方案為as(k)，將ZLP(k)定義為問題(k)的LP松弛

⑤ifZLP(k)≥Z*then

⑥剪除節(jié)點k

⑦else ifZLP(k)

⑨剪除節(jié)點k

⑩else ifZLP(k)

分支定界法是求解0-1規(guī)劃問題最主要的方法之一，通過分支、定界和剪枝操作不斷縮小解空間，剔除不可能產(chǎn)生最優(yōu)解的子集，使得計算次數(shù)減少，從而極大地降低了優(yōu)化過程中的計算復(fù)雜度，最終快速獲得最優(yōu)解。該算法可保證為傳感器網(wǎng)絡(luò)資源調(diào)度問題提供一個優(yōu)化的解決方案，并且如文獻[14]所分析，分支定界法的平均計算復(fù)雜度是特別低的，所以在具有充足處理和計算能力的主節(jié)點中執(zhí)行，能夠高效獲得最優(yōu)節(jié)點激活調(diào)度方案。

一旦主節(jié)點獲得優(yōu)化的激活調(diào)度方案，調(diào)度指令將會通過SOF信道發(fā)送至數(shù)據(jù)層的軟件定義節(jié)點，部分被選中的節(jié)點將會被激活用于相應(yīng)任務(wù)的執(zhí)行。通過該方式激活節(jié)點，并調(diào)度網(wǎng)絡(luò)資源，不僅能夠滿足不同任務(wù)的監(jiān)測質(zhì)量，還能合理利用節(jié)點剩余資源，最小化網(wǎng)絡(luò)總能耗，有效延長網(wǎng)絡(luò)壽命。

3.2 簇內(nèi)資源調(diào)度

在實際無線傳感器網(wǎng)絡(luò)中，傳感器節(jié)點大都由電池供電，并且電量有限。因此，新的節(jié)點將被部署以補償一部分電量耗盡的節(jié)點。當(dāng)節(jié)點加入或離開導(dǎo)致網(wǎng)絡(luò)拓撲發(fā)生變化時，最簡單的方法是向主節(jié)點請求全局網(wǎng)絡(luò)資源調(diào)度。該方法可最小化激活節(jié)點的數(shù)量，并合理調(diào)度整個網(wǎng)絡(luò)范圍內(nèi)的資源，但是卻有以下不足之處：

(1)頻繁地執(zhí)行全局網(wǎng)絡(luò)資源調(diào)度將會導(dǎo)致主節(jié)點負載過高，產(chǎn)生網(wǎng)絡(luò)擁塞現(xiàn)象。

(2)主節(jié)點需要不斷地收集信息用于全局優(yōu)化，從而產(chǎn)生過多控制消息，導(dǎo)致高計算復(fù)雜度和能量消耗。

(3)主節(jié)點需要收集整個網(wǎng)絡(luò)的信息，導(dǎo)致調(diào)度時間過長，優(yōu)化效率較低。

因此，筆者提出了一種低復(fù)雜度的簇內(nèi)資源調(diào)度算法，而不是采用全局優(yōu)化來處理網(wǎng)絡(luò)動態(tài)事件。簇內(nèi)資源調(diào)度僅需請求局部網(wǎng)絡(luò)信息，其計算復(fù)雜度更低，優(yōu)化效率更高。此外，該算法在簇內(nèi)執(zhí)行，由簇頭完成資源調(diào)度，將部分主節(jié)點控制功能下放到了簇頭節(jié)點處，實現(xiàn)了數(shù)據(jù)層擴展以緩解主節(jié)點控制負載。

3.2.1 節(jié)點加入

首先考慮節(jié)點作為網(wǎng)絡(luò)參與者被部署到網(wǎng)絡(luò)中的情況。盡管讓這些節(jié)點仍然保持休眠狀態(tài)不會對當(dāng)前網(wǎng)絡(luò)監(jiān)測質(zhì)量產(chǎn)生影響，但實際上很少有減少網(wǎng)絡(luò)中激活節(jié)點數(shù)量的機會。因此，當(dāng)節(jié)點加入時，可以考慮在不降低監(jiān)測質(zhì)量的前提下，減少激活節(jié)點數(shù)量以降低能耗。

圖3 節(jié)點加入示意圖

如圖3所示，兩個目標(biāo)a、b分別由兩個激活的節(jié)點A和B監(jiān)測，節(jié)點C作為新節(jié)點加入網(wǎng)絡(luò)，當(dāng)它的監(jiān)測范圍足以覆蓋這兩個目標(biāo)并提供同等水平的監(jiān)測質(zhì)量時，便可以選擇關(guān)閉節(jié)點A和B，而僅使節(jié)點C激活，從而減少激活節(jié)點數(shù)量，降低能量消耗，并優(yōu)化資源部署。

當(dāng)新節(jié)點部署時，為充分利用上述機會改善網(wǎng)絡(luò)性能，筆者提出了一種靈活高效的簇內(nèi)資源調(diào)度算法來解決傳感器節(jié)點加入事件。具體過程如下：

步驟1 以圖3為例，當(dāng)新加入節(jié)點C部署到網(wǎng)絡(luò)中時，它首先將自身信息(包括位置、內(nèi)存容量、剩余電量)上傳至主節(jié)點和簇內(nèi)控制節(jié)點(簇頭)處。

步驟2 利用節(jié)點位置信息，簇頭能夠發(fā)現(xiàn)節(jié)點C監(jiān)測范圍內(nèi)潛在的監(jiān)測目標(biāo)，如圖3中的目標(biāo)a和b。以這些潛在目標(biāo)為中心，簇頭還能夠發(fā)現(xiàn)可以覆蓋這些目標(biāo)的其他節(jié)點，例如圖3中的節(jié)點A和B。

步驟3 基于上述信息，簇頭節(jié)點可建立起一個子圖，包括節(jié)點集合S′、任務(wù)t中目標(biāo)集合G′t，以及相應(yīng)在子圖中應(yīng)該滿足的監(jiān)測質(zhì)量λ′t，即

(24)

步驟4 簇頭節(jié)點只需解決子圖上的簇內(nèi)優(yōu)化問題，便可以根據(jù)實際情況減少激活節(jié)點數(shù)量，在降低網(wǎng)絡(luò)能耗的同時，保證每個任務(wù)的監(jiān)測質(zhì)量。

步驟5 完成簇內(nèi)資源調(diào)度后，如果節(jié)點C需要切換為激活狀態(tài)，以便使其它兩個或更多節(jié)點被關(guān)閉，則激活該節(jié)點以降低能耗，并將優(yōu)化結(jié)果廣播到簇內(nèi)節(jié)點以調(diào)整其監(jiān)測策略。否則，節(jié)點C不需要被激活，集合S′中的節(jié)點仍然使用現(xiàn)有的監(jiān)測策略。

簇內(nèi)資源調(diào)度具有和全局網(wǎng)絡(luò)資源調(diào)度相同的目標(biāo)和約束，但是由于簇內(nèi)優(yōu)化中變量和約束條件的數(shù)量非常有限，所以即使是資源有限的簇頭節(jié)點，也可以很容易地解決這個優(yōu)化問題。并且由于變量和約束條件的減少，使得算法執(zhí)行時間大大降低，從而提高了再調(diào)度的效率。

3.2.2 節(jié)點離開

考慮節(jié)點由于能量耗盡或人為破壞而從網(wǎng)絡(luò)中消失的情況。同樣采用簇內(nèi)資源調(diào)度來補償節(jié)點消失后任務(wù)監(jiān)測質(zhì)量的下降，同時最小化激活節(jié)點的數(shù)量。如果簇內(nèi)資源調(diào)度無法保證監(jiān)測質(zhì)量，則在主節(jié)點處采用全局網(wǎng)絡(luò)資源調(diào)度策略滿足監(jiān)測質(zhì)量要求。相應(yīng)過程詳細描述如下：

步驟1 當(dāng)節(jié)點x的剩余能量低于閾值時，便發(fā)送一個報警消息告知簇頭。能量閾值由以下公式給出：

Eth=Eavg-Es td,

(25)

其中，Eavg表示全部激活節(jié)點剩余能量的平均值，Es td是所有激活節(jié)點剩余能量的標(biāo)準(zhǔn)差。能量低于該閾值的節(jié)點，將無法完成正常的監(jiān)測操作。

步驟2 簇頭節(jié)點收到報警消息后，采用簇內(nèi)資源調(diào)度算法，在子圖上確定節(jié)點x消失后需要調(diào)度哪些節(jié)點以保證任務(wù)監(jiān)測質(zhì)量。

步驟3 如果簇內(nèi)資源調(diào)度返回可行的解決方案，則通過簇頭將優(yōu)化結(jié)果廣播給簇內(nèi)成員節(jié)點，而節(jié)點x則繼續(xù)工作，直至其電量耗盡。否則，簇頭節(jié)點將通過安全信道發(fā)送消息來告知主節(jié)點簇內(nèi)優(yōu)化失敗。主節(jié)點隨即采用全局優(yōu)化來調(diào)度網(wǎng)絡(luò)資源，并激活節(jié)點以保證任務(wù)監(jiān)測質(zhì)量。

綜上所述，當(dāng)節(jié)點加入時，可通過簇內(nèi)資源調(diào)度在不影響監(jiān)測質(zhì)量的情況下，減少激活節(jié)點數(shù)量以優(yōu)化資源部署；當(dāng)節(jié)點離開時，通過簇內(nèi)資源調(diào)度激活節(jié)點，補償因節(jié)點離開導(dǎo)致的監(jiān)測質(zhì)量下降。簇內(nèi)資源調(diào)度算法不僅降低了主節(jié)點的控制開銷，還提高了對網(wǎng)絡(luò)動態(tài)事件的響應(yīng)速度。

算法2通過簇內(nèi)資源調(diào)度解決網(wǎng)絡(luò)動態(tài)事件。

①while 節(jié)點加入 do ①while 節(jié)點離開(Ei

② 上傳新加入節(jié)點信息至簇頭和主節(jié)點 ② 低能量節(jié)點上傳告警信息至簇頭

③ 簇頭執(zhí)行拓撲發(fā)現(xiàn)過程 ③ 簇頭采用簇內(nèi)資源調(diào)度獲得優(yōu)化方案

④ 創(chuàng)建子圖，并保證子圖監(jiān)測質(zhì)量，即 ④ if 簇內(nèi)資源調(diào)度返回可行解決方案 then

⑤ 解決子圖上的簇內(nèi)優(yōu)化問題 ⑥ else if 簇內(nèi)優(yōu)化失敗 then

⑤ if 新加入節(jié)點需激活 then ⑧ 主節(jié)點通過全局優(yōu)化保證監(jiān)測質(zhì)量

⑦ 激活節(jié)點并調(diào)整監(jiān)測策略 ⑨ end if

⑨ 在子圖上保持現(xiàn)有監(jiān)測策略

⑩ end if

4 數(shù)值結(jié)果分析

采用數(shù)值仿真的方式評估算法性能，仿真工具為Matlab2016b，仿真參數(shù)如表1所示。在100 m×100 m的區(qū)域內(nèi)，200個節(jié)點隨機分布，節(jié)點包含一個狀態(tài)數(shù)組，用于存儲能量、內(nèi)存、坐標(biāo)和監(jiān)測速率等信息；任務(wù)隨機生成，每個任務(wù)包含多個目標(biāo)，并隨機分布于仿真區(qū)域中，每個任務(wù)帶有一個屬性數(shù)組，包括監(jiān)測速率、監(jiān)測持續(xù)時間和監(jiān)測質(zhì)量要求，以及任務(wù)所需內(nèi)存大小。

表1 仿真參數(shù)設(shè)置

4.1 SDWSN控制開銷分析

為評估RS-HSDWSN的控制開銷，對比算法包括文獻[7]提出的基于軟件定義網(wǎng)絡(luò)的睡眠調(diào)度機制(SDN based Energy Consumed uniformly-Connected K-Neighborhood, SDN-ECCKN)、文獻[15]提出的基于軟件定義網(wǎng)絡(luò)的無線傳感網(wǎng)非均勻分簇協(xié)議(SDN-based Unequal Clustering Routing protocol, SDUCR)和傳統(tǒng)無線傳感器網(wǎng)絡(luò)，SDUCR同樣是在軟件定義傳感網(wǎng)中采用了分簇結(jié)構(gòu)，SDN-ECCKN為軟件定義傳感網(wǎng)中未分簇的睡眠調(diào)度策略，傳統(tǒng)無線傳感器網(wǎng)絡(luò)作為分析網(wǎng)絡(luò)控制開銷的對比基準(zhǔn)。從圖4中可以看出，傳統(tǒng)無線傳感器網(wǎng)絡(luò)的控制開銷隨時間快速增加，因為其采用分布式處理，節(jié)點之間需要交換大量的控制信息。筆者提出的RS-HSDWSN和SDUCR均在SDWSN中采用了分簇結(jié)構(gòu)，其控制開銷主要來自于拓撲發(fā)現(xiàn)和分簇建立過程，但是RS-HSDWSN的開銷更低，因為筆者采用的分簇機制考慮因素更全面，能夠更加合理地均衡簇頭能耗。與SDUCR相比，出現(xiàn)簇頭剩余能量低于閾值的情況更少，因此，減少了大量分簇結(jié)構(gòu)重建時的控制開銷。此外，RS-HSDWSN的控制開銷更是遠低于未分簇的SDN-ECCKN，因為簇頭節(jié)點通過保留部分控制功能緩解了主節(jié)點的控制開銷。

圖4 控制開銷對比

4.2 全局資源調(diào)度性能分析

圖5 全局網(wǎng)絡(luò)資源調(diào)度能量效率

圖6 資源利用率

4.3 簇內(nèi)資源調(diào)度性能分析

圖7 即時再調(diào)度時間變化曲線

簇內(nèi)資源調(diào)度能夠在節(jié)點加入或離開后快速完成資源優(yōu)化，圖7左圖為全局和簇內(nèi)資源調(diào)度的即時再調(diào)度時間變化曲線。為對比清晰，圖7右圖表示節(jié)點一跳鄰居范圍內(nèi)的局部資源調(diào)度策略。再調(diào)度時間表示網(wǎng)絡(luò)動態(tài)事件發(fā)生后，新優(yōu)化方案的計算時間。在500個時間單元上，動態(tài)事件隨機產(chǎn)生。從圖7左圖中可以看出，和全局網(wǎng)絡(luò)資源調(diào)度相比，絕大多數(shù)情況下，簇內(nèi)資源調(diào)度的再調(diào)度時間更短，因為簇內(nèi)優(yōu)化僅需請求局部網(wǎng)絡(luò)信息，使得其優(yōu)化效率更高。但是，極少數(shù)情況下，簇內(nèi)資源調(diào)度的時間要略長于全局資源調(diào)度，比如時間節(jié)點270處，因為在這種情況下，簇內(nèi)資源調(diào)度未能獲得可行的優(yōu)化方案，所以必須隨即動用全局網(wǎng)絡(luò)資源調(diào)度以保證任務(wù)監(jiān)測質(zhì)量。圖7右圖所示的局部資源調(diào)度表示某個節(jié)點消失后，在其一跳鄰居范圍內(nèi)尋找替代方案。與全局優(yōu)化相比，該方式能夠提高優(yōu)化效率，但大部分情況下其再調(diào)度時間要遠高于簇內(nèi)資源調(diào)度，因為在節(jié)點一跳鄰居范圍內(nèi)并非總能獲得最優(yōu)方案。

5 結(jié)束語

為了提高網(wǎng)絡(luò)資源利用率，并靈活響應(yīng)網(wǎng)絡(luò)動態(tài)事件，筆者提出了層次型軟件定義無線傳感器網(wǎng)絡(luò)資源調(diào)度策略。以分簇的方式實現(xiàn)數(shù)據(jù)層擴展，緩解集中式控制器負載。RS-HSDWSN在保證監(jiān)測質(zhì)量的前提下同時執(zhí)行多個任務(wù)，并最小化激活節(jié)點的數(shù)量，實現(xiàn)最佳的網(wǎng)絡(luò)及節(jié)點資源調(diào)度。最后，通過簇內(nèi)優(yōu)化靈活高效地解決網(wǎng)絡(luò)動態(tài)事件，保留了傳統(tǒng)無線傳感器網(wǎng)絡(luò)分布式處理的優(yōu)勢。與傳統(tǒng)基于特定任務(wù)的無線傳感網(wǎng)相比，所提出的激活調(diào)度策略解決了冗余部署問題，能夠?qū)崿F(xiàn)更低的能量消耗，以及更加靈活的網(wǎng)絡(luò)管理。