軟件定義傳感器網絡重配置算法研究

沈連豐，朱亞萍，丁兆明，燕鋒，鄧曙光

（1. 東南大學移動通信國家重點實驗室，江蘇 南京 210096；2. 湖南城市學院通信與電子工程學院，湖南 益陽 413000）

軟件定義傳感器網絡重配置算法研究

沈連豐1，朱亞萍1，丁兆明1，燕鋒1，鄧曙光2

（1. 東南大學移動通信國家重點實驗室，江蘇 南京 210096；2. 湖南城市學院通信與電子工程學院，湖南 益陽 413000）

為了提高無線傳感器網絡的性能及其適應性，提出一種軟件定義傳感器網絡的架構并重點研究其網絡重配置算法。算法首先運用Voronoi圖理論，尋求SDSN全覆蓋問題中保證網絡能量均衡的最優感知半徑分配，以達到目標區域的K重覆蓋；其次基于單純復形理論，提出一種基于邊緣鏈群最小生成元和節點度的集中控制方法，以最簡練的網絡拓撲結構為目標，同時保證整個系統的連通性以及突發區域的頑健性；考慮SDSN中路由協議在動態環境的自適應性，提出一種基于多業務QoS的SDSN路由優化算法并進行了仿真，結果表明所提路由算法能夠有效分配資源，滿足多業務QoS需求并延長網絡的生命周期。

軟件定義傳感器網絡；覆蓋優化；拓撲控制；路由優化

1 引言

無線傳感器網絡（WSN，wireless sensor networks）一般具有大規模、自組織、隨機部署等特點[1]，但受到環境復雜、傳感器節點資源有限、網絡拓撲經常發生變化等影響，使其應用受到極大挑戰[2]，因而拓撲控制等技術成為研究熱點。拓撲控制通過功率控制、節點休眠調度等機制盡可能減少傳感器節點的能量消耗，同時作用于媒體訪問控制（MAC，media access control）層和路由層之間，能有效降低通信干擾、提高MAC協議和路由協議的效率，并為路由層提供足夠的路由更新信息，而路由信息表的變化又反過來作用于拓撲控制機制，影響網絡的連通性和能量消耗等[3,4]。然而，傳統的WSN在網絡部署之后，其節點行為和由這些節點所提供的網絡功能很難發生改變，導致了網絡資源利用率低、策略更改困難和網絡難于管理[5]，這主要源于WSN網絡節點固有的分布式屬性，每一個節點都是一個獨立的自治系統，不利于網絡功能的靈活擴展。

軟件定義網絡（SDN，software-defined network）技術可以將網絡控制從以連接過程為核心的閉合模式轉變成以組網過程為核心的開放模式。SDN將傳統的緊耦合網絡架構解耦成應用、控制、基礎轉發設施3層分離架構[6]，實現網絡應用的可編程、整體網絡控制的中心式管控以及節點網絡單元的簡單化、通用化和低成本化。將SDN與WSN相結合，可進一步提高無線傳感器網絡的能量利用效率，簡化硬件結構，降低成本，并且有機地整合網內節點的分布式管理機制，實現統一的網絡管理控制系統，從而提高WSN的信息采集和管理效率，形成全網優化的無線傳輸和資源分配。

本文基于 SDN技術，提出一種基于軟件定義網絡的無線傳感器網絡架構及其網絡重配置算法以解決覆蓋優化、拓撲控制和路由選擇等問題。該網絡簡稱軟件定義傳感器網絡（SDSN，software-defined sensor network），所提算法運用Voronoi圖理論、單純復形理論并考慮SDSN中路由協議的自適應性及其在動態環境下的性能，以達到目標區域的K重覆蓋、全局節點功率最優、保證多個業務同時進行數據傳遞以及各自QoS（quality of service）的最大化等目標。

2 相關工作

軟件定義傳感器網絡是近年提出的新概念，目前已成為研究熱點之一。如文獻[7]給出了一種軟件定義無線傳感器網絡（SD-WSN，software-defined WSN）架構，該架構包含應用層、控制平面和數據平面 3部分，控制平面和數據平面之間通過 SOF（sensor OpenFlow）接口協議互連，從而實現了下層網絡單元的可編程；文獻[8]提出了軟件定義傳感器網絡架構的概念，其所述的軟件定義傳感器網絡中傳感器節點可以通過空中下載動態實現系統采集任務的轉變；文獻[9]定義了控制平面的角色生成和傳送機制，以及可配置的傳感器節點的硬件實現單元；文獻[10]從SDN和WSN模型結合實現的角度對WSN網絡拓撲、路由和傳輸任務等方面獲得的有益性進行了分析，結果表明在WSN中采用軟件定義的網絡架構有利于WSN網絡中路由問題和傳輸問題的解決，能夠降低網絡成本和能量消耗。

目前，關于SDSN的研究工作主要集中在方案可行性方面，對于如何利用軟件定義的優勢解決 WSN中幾個重要問題方面的研究涉及尚少。為此，本文在SDSN網絡架構下對其重配置算法進行較為深入的研究，包括覆蓋優化、網絡拓撲和路由協議等。

覆蓋可以看成是對網絡服務質量的一種度量，其重要因素之一是網絡對周邊事物的感知能力[11]。在WSN節點覆蓋問題中，已有不少典型的計算方法，如最壞與最佳情況覆蓋[12]、連通傳感器覆蓋控制算法[13]等，但其優化策略多是通過網絡節點的初始部署來實現的，未考慮網絡拓撲發生變化或者網絡突發事件發生時如何實現網絡的實時覆蓋優化。近期關于網絡覆蓋問題的研究注重對覆蓋空洞的檢測和修復，提出了基于各種理論的空洞檢測和修復方法，如基于同調理論的覆蓋空洞檢測算法[14]、基于Voronoi圖的分布式節點協同空洞檢測和修復算法[15]、多目標網絡覆蓋質量約束下可編程節點執行多個重編程任務時所需能量消耗的最小化問題[16]等。

傳統的WSN網絡拓撲控制，主要通過分布式的功率調節控制、分級拓撲控制或者功率模式控制方法來延長無線傳感器網絡的生命周期，提高其能量效率[17]。由于采用分布式的方法，網絡節點不能有效地獲取全網節點在位置、剩余能量、感知范圍、發射功率等方面的信息，單節點只能根據自身以及其相鄰節點的信息進行局部的網絡控制，網絡的性能不能達到全局最優。關于拓撲控制算法的研究通常基于隨機圖理論模型[18]，例如基于鄰近圖的功率控制算法等。近年來已有更多的拓撲模型被應用于WSN的拓撲控制研究中。如文獻[19]將博弈理論模型應用于拓撲控制研究，提出了一種非合作式博弈的分布式拓撲控制方法，用于動態設計高效和能量均衡的網絡拓撲；文獻[20]提出了一種單純復形理論應用的簡化算法，用來刪除網絡拓撲中多余的節點，并保持拓撲結構的不變性。

WSN路由算法的目的是尋找優化路徑以將有用信息從源節點發到目的節點。經典的路由協議包括低功耗自適應分層路由協議[4]、基于地理位置和能量信息的路由協議等[21]。隨著SDN研究的深入，其路由協議的研究也受到重視。文獻[22]提出一種將SDN技術用于ad hoc 網絡（SDNAN, softwaredefined networking in ad hoc networks）的路由協議，可以動態調整路由規則來適應不同的用戶需求。文獻[23]提出一種基于 SDN 技術的路由算法，用于Internet 中自治系統間的路由計算。但是，現有的WSN網絡路由協議設計主要考慮如何降低整個網絡的能量消耗，而在路由協議的自適應性以及動態環境下路由協議的性能方面尚有很大的改進空間。

基于已有軟件定義傳感器網絡架構，本文提出SDSN架構，通過應用層中覆蓋優化、網絡的拓撲控制和路由協議等相關應用，設計網絡重配置算法，從而完成整個傳感器網絡參數的重新設置。本文提出一種基于Voronoi圖的動態覆蓋算法，算法中管控中心可以通過調節節點的感知范圍實現網絡的全局覆蓋優化，實現網絡資源的全局共享；提出一種基于單純復形理論的拓撲控制算法，在已求知的網絡K重覆蓋的基礎上，借助于SDSN網絡架構的全局信息，算法尋找最簡練的網絡拓撲結構，使網絡性能達到全局最優；提出一種基于多業務QoS的路由算法，利用SDSN的控制器獲取整體網絡的鏈路狀態和每個節點上的能量消耗等信息，在發生多個并發事件時提高網絡路由重配置的準確性和實時性。上述算法有機結合并通過軟件定義實現無線傳感器網絡的拓撲結構和資源的重配置，從而有效提高其性價比并拓展應用領域。

3 軟件定義傳感器網絡架構模型

圖1 SDSN體系架構

為了和SDN基本架構一致，本文提出的SDSN體系架構主體上也分為基礎設施層、控制層和應用層3層。由圖1可見，所提架構實質上是由大量軟件定義傳感器節點和集中式管控中心2部分構成，其節點結構由傳感器模塊和通用可編程數據收發單元組成，其網絡覆蓋、拓撲控制、路由協議等網絡控制技術由集中式管控中心統一配置，并將相應配置文件分發到各節點的數據收發單元，以獲得全局最優的網絡性能。這一架構的主要特點在于可根據用戶和網絡狀態需求，利用可編程控制的網絡單元，定制算法、策略、協議等內核可高度重構化的網絡支撐系統，通過OpenFlow等相關協議開發面向對象的開放式管理與業務適配接口，實現軟件定義傳感網信息的抽象化和跨層網絡控制集成化，從而建立起具備統一網絡控制能力的適應集中控制、節點網絡單元簡化、網絡管理高效、性能全局最優等特點的新型傳感器網絡架構體系，即該架構的每一層均服務于傳感器網絡的重配置，也可以說在每一層中都增加了網絡重配置單元并且用軟件來實現。

在網絡部署完畢后，管控中心通過實時配置各感知節點的感知范圍，使監測區域被SDSN感知并實現全覆蓋。

4 SDSN的網絡重配置算法

如前所述，采用所提的SDSN架構及其網絡重配置算法來解決傳感器網絡的覆蓋優化、拓撲控制和路由優化等問題，SDSN網絡重配置算法由基于Voronoi圖的動態覆蓋算法、基于單純復形理論的拓撲控制算法和基于多業務 QoS的路由算法所構成，它們有機結合，共同完成網絡的拓撲結構以及資源的重配置。

4.1 基于Voronoi圖的動態覆蓋算法

SDSN的網絡拓撲通常是動態變化的，當有節點產生移動或失效時，網絡中各節點的感知范圍需進行調整以達到對監測區域的完全感知覆蓋；同時，若網絡中某一區域產生突發事件，相關聯的節點也應實時調整自己的感知范圍，以增加對該區域的感知精度，實現對突發事件的協同感知。本文針對SDSN網絡重配置算法中的覆蓋需求，提出一種基于Voronoi圖的動態覆蓋方法，通過引入Voronoi圖理論將監測區域進行凸域劃分，并綜合考慮網絡的能量均衡和覆蓋冗余，尋求一種最優化的節點感知半徑重配置方案，來解決網絡部署或網絡拓撲變化時對監測區域的感知全覆蓋問題，以及網絡中發生突發事件時對目標事件區域進行多點協同感知、實現K重覆蓋的問題。

Voronoi圖是計算幾何中一種空間分割的重要方法，定義監測區域A和區域內隨機部署的感知節點 S = {si|i = 1,2,… , N}，通過計算集合S中元素的最鄰近距離，可以將目標區域分割為多個相鄰接的凸域，劃分后由確定的凸多邊形稱為關聯于si的Voronoi域V(si)，其中，H ( si, sj)表示線段垂直平分線的si一側的半平面，可知對于每一元素si，其Voronoi域中的任何點到si的距離都小于該點到S中其他元素的距離。若兩節點的關聯Voronoi域存在公共邊，則這兩點互為鄰居節點，連接兩兩鄰居節點的線段所形成的圖是Voronoi圖的對偶圖，稱為 Voronoi劃分對應的Delaunay三角剖分。

基于 Voronoi圖的動態覆蓋算法的執行過程如圖 2所示，算法通過實時監測網絡的全局信息，將SDSN的覆蓋優化問題分為：1）通過對區域的Voronoi劃分和構建Delaunay三角剖分，尋求區域全覆蓋問題中保證能量均衡的節點感知半徑最優化配置；2）通過Voronoi圖和多目標決策，選擇最優的節點子集并調整其感知半徑，求解突發事件區域 K重覆蓋問題的2個子問題。具體方法如下。

圖2 SDSN中基于Voronoi圖的動態覆蓋算法執行過程

1) 最優化感知半徑配置策略

SDSN覆蓋優化算法的Voronoi模型如圖3所示。對于監測區域A和區域內的感知節點集S，算法首先對監測區域進行Voronoi凸域劃分，具體的Voronoi劃分示意如圖3（a）所示，其中，實線代表Voronoi多邊形，虛線表示對應的Delaunay三角剖分。算法采用逐點插入法構建 Delaunay三角剖分，其步驟為：①構建節點集S的最小凸集，生成初始Delaunay三角剖分；②隨機排列節點集S中的所有節點；③對任一節點Sr執行內插操作：首先定位包含Sr的三角形SiSjSk，然后連接Sr和三角形各個頂點，將其剖分成3個子三角形，最后利用邊交換法規格化三角剖分。這樣，就將全覆蓋問題分解為計算局部Delaunay三角形的覆蓋問題。

一般認為在覆蓋問題中，節點的感知行為是能量消耗的主要因素，將節點si的能耗建模為感知半徑Ri的函數Pi(Ri)，引入節點的剩余能量Ei，則整個網絡的剩余生命期可以表示為

對任一Delaunay三角形 ? S1S2S3，其頂點sj的坐標為(yj)， j∈ {1,2,3}，為最小化覆蓋冗余，3個頂點的感知圓盤在三角形內交于一點，算法根據相應節點的權重 l( sj)（在網絡初始部署階段可令Rj=0）計算交點cg，使權重較小的頂點至cg的距離較近，則可得到節點sj的一種半徑分配rj=d(si, cg)，計算過程如圖3（b）所示。算法對與sj鄰接的所有Delaunay三角形進行依次計算，并在所產生的半徑分配集中選取最大值作為sj的優化半徑分配。其他節點通過依次迭代也可得到各自的優化半徑，從而網絡獲得最優的感知范圍配置方案，在保證區域全覆蓋的基礎上，可以達到能量均衡、最大化網絡生命周期的目的。特別地，對位于區域邊界處的節點sk，應將sk至V(sj) 與區域邊界交點的距離、sk至邊界頂點的距離分別與得到的優化半徑做比較，取其中的最大值作為sk的半徑，以保證區域邊界的全覆蓋。

2) 最優化節點子集決策策略

采用覆蓋重數作為區域覆蓋的性能指標。假設突發事件發生時，感知節點sn首先上報事件信息，則將sn感知范圍作為目標區域Z，sn在Voronoi圖中的M跳鄰居節點作為候選節點集Sm={s1,…, sl}，目標區域的覆蓋重數可以表示為

對任意 sm∈SM，調整其感知半徑使其中，是調整后的半徑，則調整后的節點sm可以實現對目標區域的覆蓋。管控中心綜合考慮候選節點調整半徑所付出的代價包括網絡生命期的變化及覆蓋冗余度的增加，從候選集中決策選擇最優的K-1個節點，調整其感知半徑以實現對目標事件區域的K重覆蓋。式(1)給出

了網絡的剩余生命期模型，它與節點的剩余能量 Em和能耗相關，而覆蓋冗余度的變化量在監測區域已實現全覆蓋的情況下可以表示為這樣算法可以建立相應的決策代價函數 H(L,U)進行子集決策，決策過程可以抽象為如下帶約束條件的優化模型。

目標函數

約束條件

圖3 SDSN覆蓋優化算法的Voronoi模型

通過對該優化模型的求解分析，可以尋求最優的節點子集和半徑調整方案，如果候選節點集較大，可以考慮采用啟發式算法進行子集搜索，以獲得問題的次優解。

4.2 基于單純復形理論的拓撲控制算法

SDSN網絡中的傳感器節點和節點間通信鏈路可以抽象為0-單形和1-單形，通過合理地增加或者刪除節點間的無線通信鏈路，生成一個能量高效的優化網絡拓撲結構。為了獲取SDSN網絡連通性的相關信息，引入單純鏈復形和貝蒂數的定義。給定一個單復形，它的j維單純鏈Dj是由其j維定向單形生成的拓撲空間。單純鏈Dj對應的邊緣算子?j的定義如下

其中，vi表示所對應單形的頂點。應用邊緣算子?j可以對單純復形的j維單純鏈進行降維，從而得到單純復形的單純鏈復形

單純鏈復形中 ?j：Dj→ Dj?1的核被稱為j維閉鏈群，記作 Zj； ?j+1：Dj+1→ Dj的像被稱為 j維邊緣鏈群，記作Bj。由引理 ?j?j+1= 0可知j維邊緣群屬于j維閉鏈群，即 Zj?Bj，繼而可以定義該復形的j-貝蒂數為

其中，dimZj表示 j維閉鏈群 Zj的維數，dimBj表示 j維邊緣鏈群 Bj的維數，j-貝蒂數 Bj等于 j維閉鏈群 Zj維數與 j維邊緣鏈群 Bj維數的差。在SDSN場景下，0維閉鏈群 Z0的維數就是 SDSN中傳感器節點的數量，0維邊緣鏈群B0的維數就是全網各連通分量最小連通子集的1-單形數量之和，從而0-貝蒂數0β表示SDSN中連通分量的個數，1-貝蒂數則表示二維平面上沒有無線信號覆蓋的空洞的個數。

基于上述定義，本算法提出了基于邊緣鏈群最小生成元和節點度，以最簡練的網絡拓撲結構為目標，同時保證整個系統的連通性以及突發區域頑健性的全局節點功率最優的問題，并將該最優問題分解為幾個子問題進行求解，由2個子過程來執行，即功率預配置過程和功率重配置過程。功率預配置過程確保了網絡部署和網絡結構發生變化時網絡拓撲的精簡性和連通性，功率重配置過程確保了網絡突發事件發生時突發區域網絡拓撲的頑健性。當管控中心檢測到網絡拓撲發生變化時執行功率預配置過程，刪除網絡中冗余的無線鏈路同時確保網絡的連通性；當檢測到突發事件發生時，由SDSN管控中心執行功率重配置過程，調整突發事件產生區域內節點的無線發射功率，增加區域內無線鏈路的冗余度以提高局部區域的穩定性和頑健性。

SDSN功率預配置和重配置的具體流程如下。

1) 軟件定義傳感網絡功率預配置過程

首先，SDSN管控中心根據節點的位置和初始發射功率獲取網絡中所有1-單形的節點構成，然后計算邊緣算子?0、?1的核空間維數以及像空間維數得到0β。其次，根據0β的取值判斷網絡是否連通，0β為1表示網絡連通，反之表示網絡不連通；如果網絡不是連通的，計算?1像空間的最小生成元，根據最小生成元得到各個連通分量的最小連通子集，從而確定連通分量內節點的最佳發射功率。接著，通過綜合考慮連通分量中節點的度和剩余能量來決定邊緣節點的選擇，根據邊緣節點的位置信息增大其發射功率使網絡的0-貝蒂數降為 1，這里節點的度是指包含該節點網絡中1-單形的個數。軟件定義傳感網絡功率預配置流程如圖4所示。

圖4 軟件定義傳感網絡功率預配置擬定流程

2) 軟件定義傳感網絡功率重配置過程

在確保整個網絡連通性的基礎上，SDSN管控中心根據突發事件發生的位置和范圍得到突發區域內節點的位置信息，根據突發事件的緊急程度來確定對突發區域內節點度的平均增加量。然后，以區域外節點度的變化最小為目標對突發區域內節點的發射功率進行迭代調整，同時確保每個迭代步區域內節點平均度的增量都是一樣的，經過多次迭代可以得到最優的重配置節點集以及相應的重配置功率。軟件定義傳感網絡功率重配置過程如圖 5所示。

圖5 軟件定義傳感網絡功率重配置擬定流程

4.3 基于多業務QoS的路由算法

在SDSN中，源節點到目的節點的路由選擇對于整個無線傳感器網絡系統的性能具有重要作用。在發生多個并發事件時，系統中央控制器會根據各自源節點自身業務的QoS，整體網絡的鏈路狀態和每個節點上的能量消耗等信息選擇到目的節點的路由，提高因突發事件網絡中路由重新配置的準確性和實時性。

圖 6是基于多業務 QoS的路由算法擬定系統，當有突發事件發生時，SDSN管控中心接收到源節點發起數據的發送請求，管控中心根據新的突發事件Unew以及SDSN中剩余正在進行的業務集Un′ow進行合并形成新的業務集合 Unow= Un′ow∪ Unew。每個業務集合中的元素包含該業務數據的發送端、數據的到達端和數據發送的QoS需求等網絡信息，新的業務集合存儲在管控中心中用于路由計算。

隨后，根據新的業務集合Unow管控中心集中調取網絡中的有效信息用于路由計算，如各節點剩余能量E={E1,…,EN}和各個業務的QoS需求等?？紤]到節點的可擴展性，多個無線收發裝置同時配置在一個傳感器節點成為可能，因此，基于 SDN的傳感器網路由算法將收發裝置的可擴展性加入路由算法中。由于一個無線傳感器節點可同時收、同時發或者部分收和部分發送數據，因此，不同于傳統單一收發裝置傳感器網絡的路由計算，整個網絡的路由將變得極其復雜。所以，本文將多收發裝置作為研究路由算法的一個網絡特性，同時可以看到該算法能夠退化到單一收發裝置的傳感器網絡中，具有一定的普適作用。業務QoS作為衡量該業務服務質量的標準有著較好的作用，QoS的關鍵指標主要包括：可用性、吞吐量、時延、時延變化和丟失等。本文將考慮網絡單位時間內傳輸的信息量作為業務QoS的度量準則。路由算法依據業務集中每個業務QoS需求動態分配路由給各個業務，保證最大化每個業務的QoS。

圖6 基于多業務QoS的路由算法擬定系統

考慮到節點的可擴展性，假設每個節點可以部署一個或者多個無線收發裝置（異構無線傳感器網絡中的高級節點），同時整個網絡配置K個正交子信道來進行數據的傳送。假設網絡中共有N個節點，每個節點可擁有rn個無線收發裝置，節點i所擁有的有效傳輸半徑為Ti，節點i與節點j的歐氏距離記為dij，由此可得網絡中可進行一跳傳輸的鏈路集合記為 ε= {(i, j)|dij≤ Ti,1 ≤ i, j≤ N, i ≠j} 。

考慮到SDSN干擾受限的特點，同一信道可以在相互獨立的鏈路上同時發送數據，又因為在本文中K個正交子信道都可以用來傳輸數據。因此，可以得到一個并發數據傳輸鏈路集，記為P = [1,… , p, … ,|P|]。從而可以調度每個并發鏈路集所占用的時間百分比，進而得到每個鏈路上單位時間內所能傳送信息量的上限。根據該信息量上限，可以得到最優傳輸路徑。

定義下面的二元指示變量：① 若鏈路(i, j)在并發鏈路集p上被激活且占用子信道k，為1，否

則， vk,p為0；② 若節點i在并發鏈路集p上被激

i, j

活且占用子信道k，則 xn

k,p為1，否則，為0。因為一個節點在同一時刻最多只能與一個相鄰節點在某一子信道上進行通信，由此可得

因為每個節點受到其自身無線收發裝置個數的限制，由此可以得到

如果2條鏈路可在同一子信道上同時傳輸，那么這2條鏈路必須相互獨立，此時應滿足

其中，F[(i,j),(u,w)]為指示鏈路(i,j)和鏈路(u,w)是否相互獨立的二元變量，若相互獨立則為1，否則，為0。

為描述簡單，歸一化激活鏈路在一個子信道上的數據速率為單位常量，因此，可以得到每條鏈路在單位時間內的信息量上限為

其中，λp為并發傳輸集合p所占用單位時間上的百分比數。

假設系統有M個端到端的業務流，則每個業務的源節點、目的節點和該業務 QoS可以寫為Sm=(sm,dm,Im),sm,dm=1,2,… ,N, Im> 0,m =1,2,… , M 。定義 Iim,j為業務 m在單位時間內通過鏈路(i,j)的信息量。

在無線通信網絡中，每個節點在發送或接收每個比特都應消耗一定的能量。若節點發送ψbit數據，則其消耗能量為 ET= Eψ+ αd2ψ；若節點接

elec

收ψbit數據，則其消耗能量為 ER=Eψ。因此，

elec

在單位時間內節點i發送數據所消耗的能量為

同理，可得在單位時間內節點i接收數據所消耗的能量為

在單位時間內，節點i所消耗的總能量為

用iρ表示節點i的能量負載情況為

其中，Ei為節點i剩余總能量，E為每個節點初始化能量。利用Jain公平指數，可得

在節點擁有一個或者多個無線收發裝置，即節點間可采用多個正交子信道進行通信和多種業務流同時傳送的場景下，通過平衡每個節點的剩余能量在保證每個業務 QoS的前提下延長網絡的工作壽命。

該算法可以表述如下。

目標函數

約束條件

目標函數（17）表示最大化網絡能量Jain公平指數，以達到網絡各節點剩余能量均衡；約束條件（18）表示在單位時間內m業務中流入和流出轉發節點的信息量應相等；約束條件（19）和（20）分別表示在單位時間內屬于 m業務的源節點流入和目的節點沒有相應信息量流出；約束條件（21）表示單位時間內m業務源節點流出的總信息量；約束條件（22）表示單位時間內所有業務在每個鏈路上的信息量應小于該鏈路的單位時間內信息量的上限；約束條件（23）表示每個節點上無線收發裝置個數的約束。

基于多業務QoS的路由算法執行過程如圖7所示。當網絡中有突發事件發生時，開始路由計算，管控中心搜集所需信息，依據非線性有約束規劃算法進行迭代求解，若解滿足收斂條件，則算法終止，若不滿足算法收斂條件，算法繼續；而當網絡中沒有突發事件發生時，系統則直接跳過路由計算，保持原路由不變。

5 路由算法性能仿真及其結果分析

為了驗證所提網絡重配置算法，本節以路由算法為例進行性能仿真并分析其結果，其他算法的仿真及其與已有算法的比較將另文給出。

5.1 仿真場景

圖8給出了本文所提SDSN的工作場景，其初始場景如圖8（a）所示。管控中心對SDSN節點剩余能量進行衡量，選擇了節點 a、b、c成為接入節點，剩下的SDSN節點d、e退化為普通節點，與區域內其他傳感器節點一同工作。網絡中存在若干業務，在管控中心的集中式調度下，它們分別從各自的源節點到達目的節點，系統處于穩定的工作狀態。

隨著突發事件A的到來，大量的數據需要上傳至管控中心，網絡中原有的路由已經不能滿足新的傳輸需求，管控中心需要對網絡中的路由進行優化，重新選擇接入節點，并對接入節點的發射功率、路由進行重配置，盡可能將系統中的業務數據上傳，調整后的系統場景如圖8（b）所示。

仿真采用Matlab，仿真環境設置參數如表1所示。

仿真場景如下：SDSN網絡使用單信道，并假設 10個普通節點和 4個接入節點隨機分布在（x=-50，y=-50)和（x=50，y=50)的矩形區域內，管控中心位于原點（x=0，y=0）處。各普通節點的單跳傳輸、接收距離均為20 m。網絡中業務流數目為10，即每個普通節點都有數據業務需要上傳。

圖7 基于多業務QoS的路由算法擬執行過程

圖8 SDSN工作場景

表1 仿真參數

5.2 仿真結果及其分析

根據上述的聯合功率控制的路由協議及仿真參數，對路由算法的性能進行仿真。圖9(a)表明接入節點發射功率上限為[1.6 1.6 1.6 1.6]TmW時，接入鏈路的最優傳輸速率*r?隨著迭代次數增加的變化情況?？梢园l現在迭代600次時，曲線逐漸趨于平緩，并最終收斂于[2.219, 2.278, 2.211, 2.201]Tnat/symbol。圖 9(b)為接入節點發射功率上限為[1.8, 1.8, 1.8,1.8]TmW時，接入鏈路的最優傳輸速率*r?的迭代變化情況，可以發現當接入節點發射功率上限變化時，所提算法都在1 000次迭代內獲得了最優解，這也意味著所提路由協議具有較好的收斂性。

圖9 接入節點速率收斂曲線

圖10給出接入節點功率上限與流速率關系的仿真結果。由圖可見，接入節點發射功率上限從=[1.4 1.4 1.4 1.4]TmW到=[2.6 2.6 2.6 2.6]TmW變化時，管控中心為各接入節點分配的最優流速率的變化情況，可以發現，隨著接入節點最大發射功率的增大，最優流速率也逐漸增大，系統的總吞吐量將隨之增加，表明管控中心能夠充分地對網絡中的資源加以調配，滿足區域內各業務數據上傳需求，盡可能地提高系統性能。此外，當接入節點最大發射功率相同時，管控中心為各接入節點分配的資源相差不大，表明系統能夠通過設置節點發射功率的上限有效地均衡系統中接入節點的能耗，以延長網絡的生命周期。

圖10 接入節點功率上限與流速率關系曲線

6 結束語

本文將軟件定義網絡技術融合進無線傳感器網絡，給出了軟件定義傳感器網絡的體系架構，提出了SDSN的網絡重配置算法，具體包括覆蓋優化、拓撲控制以及路由優化3個方面。對于覆蓋優化，提出了一種基于Voronoi圖的動態覆蓋算法，尋求SDSN全覆蓋問題中保證網絡能量均衡的最優感知半徑分配，并選擇最優節點子集和其感知半徑，以達到目標區域的K-覆蓋；在拓撲控制方面，基于單純復形理論，提出了一種基于邊緣鏈群最小生成元和節點度的集中控制方法，包括SDSN功率預配置過程中的邊緣鏈群最小生成元高效、次優算法，以及快速、高效的SDSN功率重配置迭代算法，保證了整個系統的連通性以及突發區域的頑健性；考慮SDSN中路由協議的自適應性以及其在動態環境下的性能，提出一種基于多業務QoS的SDSN路由優化算法，依據每個業務的QoS需求動態分配路由，從而保證多個業務同時進行數據傳遞以及各自QoS的最大化，同時平衡傳感器節點的剩余能量。以路由算法為例進行了仿真，結果表明所提路由算法能夠有效分配資源，滿足SDSN網絡中多業務QoS需求并延長網絡的生命周期。

7 致謝

東南大學移動通信國家重點實驗室博士生張瑞、劉誠毅、茆意偉、章躍躍參與了本文初稿的部分撰寫，碩士生李媚、丁翠、曹智勇、唐敏等對本文所提算法研制了實驗系統并進行了仿真，在此一并致謝。

[1] YICK J, MUKHERJEE B, GHOSAL D. Wireless sensor network survey[J]. Computer Networks, 2008, 52(12)： 2292-2230.

[2] LOCHER T, RICKENBACH P V, WATTENHOFER R. Sensor networks continue to puzzle： selected open problems[C]//International Conference on Distributed Computing and Networking (ICDCN),c2008：25-38.

[3] RAJARAMAN R. Topology control and routing in ad hoc networks： a survey[J]. ACM SIGACT News, 2002, 33(2)： 60-73.

[4] AL-KARAKI J N, KAMAL A E. Routing techniques in wireless sensor networks： a survey[J]. IEEE Wireless Communications, 2004,11(6)： 6-28.

[5] FRANK C, ROMER K. Algorithms for generic role assignment in wireless sensor networks[C]//Proc of ACM SenSys’05, c2005：230-242.

[6] SEZER S, CHOUHAN P K, RAO N, et al. Are we ready for SDN?implementation challenges for software-defined networks [J]. IEEE Communications Magazine, 2013, 51(7)： 36-43.

[7] LUO T, TAN H-P, QUEK T Q S. Sensor OpenFlow： enabling software-defined wireless sensor networks[J]. IEEE Communications Letters, 2012, 16(11)： 1896-1899.

[8] ZENG D, MIYAZAKI T, GUO S, et al. Evolution of software-defined sensor networks[C]// 2013 IEEE Ninth International Conference on Mobile Ad-hoc and Sensor Networks (MSN). Dalian, China, c2013：410-413.

[9] MIYAZAKI T, et al. A software defined wireless sensor network[C]//2014 International Conference on Computing, Networking and Communications (ICNC). Honolulu, HI, c2014： 847-852.

[10] ALEKSANDER M B, et al. Implementation technology software-defined networking in wireless sensor networks[C]//2015 IEEE 8th International Conference on Intelligent Data Acquisition and Advanced Computing Systems： Technology and Applications (IDAACS).Warsaw, c2015：448-452.

[11] MEGUERDICHIAN S, KOUSHANFAR F, POTKONJAK M, et al.Coverage problems in wireless ad hoc sensor networks[C]//IEEE Conf on Computer Communications (INFOCOM). New York, c2001： 1380-1387.

[12] LEE C, SHIN D, BAE S W, et al. Best and worst-case coverage problems for arbitrary paths in wireless sensor networks[J]. Ad Hoc Networks, 2013,(11)：1699-1714.

[13] YU J, CHEN Y, HUANG B. On connected target k-coverage in heterogeneous wireless sensor networks[C]// 2015 International Conference on Identification, Information, and Knowledge in the Internet of Things (IIKI). Beijing, c2015：262-265.

[14] YAN F, VERGNE A, MARTINS P, et al. Homology-based distributed coverage hole detection in wireless sensor networks[J]. IEEE/ACM Transactions on Networking, 2015, 23(6)： 1705-1718.

[15] QIU C X, SHEN H Y, CHEN K. An energy-efficient and distributed cooperation mechanism for k-coverage hole detection and healing in WSNs[C]//2015 IEEE 12th International Conference on Mobile Ad Hoc and Sensor Systems (MASS). Dallas, TX, c2015： 73-81.

[16] ZENG D, LI P, GUO S, et al. Energy minimization in multi-task software-defined sensor networks[J]. IEEE Transactions on Computers,2015, 64(11)： 3128-3139.

[17] AZIZ A, SEKERCIOGLU Y A, FITZPATRICK P, et al. A survey on distributed topology control techniques for extending the lifetime of battery powered wireless sensor networks[J]. IEEE Communications Surveys and Tutorials, 2013, 15(1)： 121-144.

[18] 甘從輝, 鄭國強, 唐盛禹. 無線傳感器網絡的拓撲控制研究[J]. 計算機應用研究, 2009, 26(9)： 3214-3218.GAN C H, ZHENG G Q, TANG S Y. Survey of topology control in wireless sensor networks[J]. Applications Research of Computers,2009, 26(9)： 3214-3218.

[19] XU M, YANG Q, KWAK K S. Distributed topology control with lifetime extension based on non-cooperative game for wireless sensor networks[J]. IEEE Sensors Journal, 2016, 16(9)： 3332-3342.

[20] VERGNE A, DECREUSEFOND L, MARTINS P. Reduction algorithm for simplicial complexes[C]//2013 Proceedings IEEE INFOCOM, Turin, c2013：475-479.

[21] SANCHEZ J A, RUIZ P M, STOJMNENOVIC I. GMR： geographic multicast routing for wireless sensor networks[C]//2006 3rd Annual IEEE Communications Society on Sensor and Ad Hoc Communications and Networks. Reston, VA, c2006：20-29.

[22] BASKETT P, SHANG Y, ZENG W J, et al. SDNAN： software-defined networking in ad hoc networks of smartphones[C]//2013 IEEE 10th Consumer Communications and Networking Conference (CCNC). Las Vegas, NV, c2013：861-862.

[23] BENNESBY R, FONSECA P, MOTA E, et al. An inter-AS routing component for software-defined networks[C]//2012 IEEE Network Operations and Management Symposium. Maui, HI, c2012：138-145.

Study on network reconfiguration algorithms in software-defined sensor networks

SHEN Lian-feng1, ZHU Ya-ping1, DING Zhao-ming1, YAN Feng1, DENG Shu-guang2
(1. National Mobile Communications Research Laboratory, Southeast University, Nanjing 210096, China;2. College of Communications and Electronics Engineering, Hunan City University, Yiyang 413000, China)

In order to improve the performances and adaptabilities of wireless sensor networks the architecture of software-defined sensor network (SDSN) was proposed and the studies were focused on the network reconfiguration algorithm of SDSN. In the algorithm, the theory of Voronoi diagram was first used to search the optimal allocation of sensing radius to achieve K-coverage on the target region. Then, based on the theory of simplicial complex, a centralized control mechanism based on the minimal generator of boundary chain group and the node degree was proposed to simplify the architecture of network topology and to ensure the connectivity of the whole system and the robustness of the emergency region. Considering the adaptability in dynamic environment of routing protocols in SDSN, a routing optimization algorithm for SDSN was proposed, which was based on quality of service (QoS) of multi-service. Simulation results show that the proposed routing algorithm can efficiently allocate resources to satisfy the requirements of multi-service’s QoS and to prolong the lifetime of network.

software-defined sensor networks, coverage optimization, topology control, routing optimization

s: The National Natural Science Foundation of China (No.61471164), The Research Fund of National Mobile Communication Research Laboratory, Southeast University (No.2016B02)

TP393

A

10.11959/j.issn.1000-436x.2016132

2016-05-05；

2016-07-01

國家自然科學基金項目資助（No.61471164）；東南大學移動通信國家重點實驗室自主研究基金資助項目（No.2016B02）

沈連豐（1952-），男，江蘇邳州人，東南大學教授、博士生導師，主要研究方向為寬帶移動通信、短距離無線通信和泛在網絡等。

朱亞萍（1990-），女，江蘇建湖人，東南大學博士生，主要研究方向為寬帶移動通信、無線傳感器網絡定位等。

丁兆明（1978-），男，山東日照人，東南大學博士生，主要研究方向為無線傳感器網絡、拓撲控制等。

燕鋒（1983-），男，湖北天門人，博士，東南大學副研究員，主要研究方向為無線傳感器網絡、異構網絡等。

鄧曙光（1972-），男，湖南益陽人，博士，湖南城市學院教授，主要研究方向為無線傳感器網絡、車域網、異構網絡等。