軟件定義傳感器網(wǎng)絡(luò)重配置算法研究

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

（1. 東南大學(xué)移動(dòng)通信國(guó)家重點(diǎn)實(shí)驗(yàn)室，江蘇 南京 210096；2. 湖南城市學(xué)院通信與電子工程學(xué)院，湖南 益陽(yáng) 413000）

軟件定義傳感器網(wǎng)絡(luò)重配置算法研究

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

（1. 東南大學(xué)移動(dòng)通信國(guó)家重點(diǎn)實(shí)驗(yàn)室，江蘇 南京 210096；2. 湖南城市學(xué)院通信與電子工程學(xué)院，湖南 益陽(yáng) 413000）

為了提高無(wú)線傳感器網(wǎng)絡(luò)的性能及其適應(yīng)性，提出一種軟件定義傳感器網(wǎng)絡(luò)的架構(gòu)并重點(diǎn)研究其網(wǎng)絡(luò)重配置算法。算法首先運(yùn)用Voronoi圖理論，尋求SDSN全覆蓋問(wèn)題中保證網(wǎng)絡(luò)能量均衡的最優(yōu)感知半徑分配，以達(dá)到目標(biāo)區(qū)域的K重覆蓋；其次基于單純復(fù)形理論，提出一種基于邊緣鏈群最小生成元和節(jié)點(diǎn)度的集中控制方法，以最簡(jiǎn)練的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)為目標(biāo)，同時(shí)保證整個(gè)系統(tǒng)的連通性以及突發(fā)區(qū)域的頑健性；考慮SDSN中路由協(xié)議在動(dòng)態(tài)環(huán)境的自適應(yīng)性，提出一種基于多業(yè)務(wù)QoS的SDSN路由優(yōu)化算法并進(jìn)行了仿真，結(jié)果表明所提路由算法能夠有效分配資源，滿足多業(yè)務(wù)QoS需求并延長(zhǎng)網(wǎng)絡(luò)的生命周期。

軟件定義傳感器網(wǎng)絡(luò)；覆蓋優(yōu)化；拓?fù)淇刂疲宦酚蓛?yōu)化

1 引言

無(wú)線傳感器網(wǎng)絡(luò)（WSN，wireless sensor networks）一般具有大規(guī)模、自組織、隨機(jī)部署等特點(diǎn)[1]，但受到環(huán)境復(fù)雜、傳感器節(jié)點(diǎn)資源有限、網(wǎng)絡(luò)拓?fù)浣?jīng)常發(fā)生變化等影響，使其應(yīng)用受到極大挑戰(zhàn)[2]，因而拓?fù)淇刂频燃夹g(shù)成為研究熱點(diǎn)。拓?fù)淇刂仆ㄟ^(guò)功率控制、節(jié)點(diǎn)休眠調(diào)度等機(jī)制盡可能減少傳感器節(jié)點(diǎn)的能量消耗，同時(shí)作用于媒體訪問(wèn)控制（MAC，media access control）層和路由層之間，能有效降低通信干擾、提高M(jìn)AC協(xié)議和路由協(xié)議的效率，并為路由層提供足夠的路由更新信息，而路由信息表的變化又反過(guò)來(lái)作用于拓?fù)淇刂茩C(jī)制，影響網(wǎng)絡(luò)的連通性和能量消耗等[3,4]。然而，傳統(tǒng)的WSN在網(wǎng)絡(luò)部署之后，其節(jié)點(diǎn)行為和由這些節(jié)點(diǎn)所提供的網(wǎng)絡(luò)功能很難發(fā)生改變，導(dǎo)致了網(wǎng)絡(luò)資源利用率低、策略更改困難和網(wǎng)絡(luò)難于管理[5]，這主要源于WSN網(wǎng)絡(luò)節(jié)點(diǎn)固有的分布式屬性，每一個(gè)節(jié)點(diǎn)都是一個(gè)獨(dú)立的自治系統(tǒng)，不利于網(wǎng)絡(luò)功能的靈活擴(kuò)展。

軟件定義網(wǎng)絡(luò)（SDN，software-defined network）技術(shù)可以將網(wǎng)絡(luò)控制從以連接過(guò)程為核心的閉合模式轉(zhuǎn)變成以組網(wǎng)過(guò)程為核心的開(kāi)放模式。SDN將傳統(tǒng)的緊耦合網(wǎng)絡(luò)架構(gòu)解耦成應(yīng)用、控制、基礎(chǔ)轉(zhuǎn)發(fā)設(shè)施3層分離架構(gòu)[6]，實(shí)現(xiàn)網(wǎng)絡(luò)應(yīng)用的可編程、整體網(wǎng)絡(luò)控制的中心式管控以及節(jié)點(diǎn)網(wǎng)絡(luò)單元的簡(jiǎn)單化、通用化和低成本化。將SDN與WSN相結(jié)合，可進(jìn)一步提高無(wú)線傳感器網(wǎng)絡(luò)的能量利用效率，簡(jiǎn)化硬件結(jié)構(gòu)，降低成本，并且有機(jī)地整合網(wǎng)內(nèi)節(jié)點(diǎn)的分布式管理機(jī)制，實(shí)現(xiàn)統(tǒng)一的網(wǎng)絡(luò)管理控制系統(tǒng)，從而提高WSN的信息采集和管理效率，形成全網(wǎng)優(yōu)化的無(wú)線傳輸和資源分配。

本文基于 SDN技術(shù)，提出一種基于軟件定義網(wǎng)絡(luò)的無(wú)線傳感器網(wǎng)絡(luò)架構(gòu)及其網(wǎng)絡(luò)重配置算法以解決覆蓋優(yōu)化、拓?fù)淇刂坪吐酚蛇x擇等問(wèn)題。該網(wǎng)絡(luò)簡(jiǎn)稱軟件定義傳感器網(wǎng)絡(luò)（SDSN，software-defined sensor network），所提算法運(yùn)用Voronoi圖理論、單純復(fù)形理論并考慮SDSN中路由協(xié)議的自適應(yīng)性及其在動(dòng)態(tài)環(huán)境下的性能，以達(dá)到目標(biāo)區(qū)域的K重覆蓋、全局節(jié)點(diǎn)功率最優(yōu)、保證多個(gè)業(yè)務(wù)同時(shí)進(jìn)行數(shù)據(jù)傳遞以及各自QoS（quality of service）的最大化等目標(biāo)。

2 相關(guān)工作

軟件定義傳感器網(wǎng)絡(luò)是近年提出的新概念，目前已成為研究熱點(diǎn)之一。如文獻(xiàn)[7]給出了一種軟件定義無(wú)線傳感器網(wǎng)絡(luò)（SD-WSN，software-defined WSN）架構(gòu)，該架構(gòu)包含應(yīng)用層、控制平面和數(shù)據(jù)平面 3部分，控制平面和數(shù)據(jù)平面之間通過(guò) SOF（sensor OpenFlow）接口協(xié)議互連，從而實(shí)現(xiàn)了下層網(wǎng)絡(luò)單元的可編程；文獻(xiàn)[8]提出了軟件定義傳感器網(wǎng)絡(luò)架構(gòu)的概念，其所述的軟件定義傳感器網(wǎng)絡(luò)中傳感器節(jié)點(diǎn)可以通過(guò)空中下載動(dòng)態(tài)實(shí)現(xiàn)系統(tǒng)采集任務(wù)的轉(zhuǎn)變；文獻(xiàn)[9]定義了控制平面的角色生成和傳送機(jī)制，以及可配置的傳感器節(jié)點(diǎn)的硬件實(shí)現(xiàn)單元；文獻(xiàn)[10]從SDN和WSN模型結(jié)合實(shí)現(xiàn)的角度對(duì)WSN網(wǎng)絡(luò)拓?fù)洹⒙酚珊蛡鬏斎蝿?wù)等方面獲得的有益性進(jìn)行了分析，結(jié)果表明在WSN中采用軟件定義的網(wǎng)絡(luò)架構(gòu)有利于WSN網(wǎng)絡(luò)中路由問(wèn)題和傳輸問(wèn)題的解決，能夠降低網(wǎng)絡(luò)成本和能量消耗。

目前，關(guān)于SDSN的研究工作主要集中在方案可行性方面，對(duì)于如何利用軟件定義的優(yōu)勢(shì)解決 WSN中幾個(gè)重要問(wèn)題方面的研究涉及尚少。為此，本文在SDSN網(wǎng)絡(luò)架構(gòu)下對(duì)其重配置算法進(jìn)行較為深入的研究，包括覆蓋優(yōu)化、網(wǎng)絡(luò)拓?fù)浜吐酚蓞f(xié)議等。

覆蓋可以看成是對(duì)網(wǎng)絡(luò)服務(wù)質(zhì)量的一種度量，其重要因素之一是網(wǎng)絡(luò)對(duì)周邊事物的感知能力[11]。在WSN節(jié)點(diǎn)覆蓋問(wèn)題中，已有不少典型的計(jì)算方法，如最壞與最佳情況覆蓋[12]、連通傳感器覆蓋控制算法[13]等，但其優(yōu)化策略多是通過(guò)網(wǎng)絡(luò)節(jié)點(diǎn)的初始部署來(lái)實(shí)現(xiàn)的，未考慮網(wǎng)絡(luò)拓?fù)浒l(fā)生變化或者網(wǎng)絡(luò)突發(fā)事件發(fā)生時(shí)如何實(shí)現(xiàn)網(wǎng)絡(luò)的實(shí)時(shí)覆蓋優(yōu)化。近期關(guān)于網(wǎng)絡(luò)覆蓋問(wèn)題的研究注重對(duì)覆蓋空洞的檢測(cè)和修復(fù)，提出了基于各種理論的空洞檢測(cè)和修復(fù)方法，如基于同調(diào)理論的覆蓋空洞檢測(cè)算法[14]、基于Voronoi圖的分布式節(jié)點(diǎn)協(xié)同空洞檢測(cè)和修復(fù)算法[15]、多目標(biāo)網(wǎng)絡(luò)覆蓋質(zhì)量約束下可編程節(jié)點(diǎn)執(zhí)行多個(gè)重編程任務(wù)時(shí)所需能量消耗的最小化問(wèn)題[16]等。

傳統(tǒng)的WSN網(wǎng)絡(luò)拓?fù)淇刂疲饕ㄟ^(guò)分布式的功率調(diào)節(jié)控制、分級(jí)拓?fù)淇刂苹蛘吖β誓Ｊ娇刂品椒▉?lái)延長(zhǎng)無(wú)線傳感器網(wǎng)絡(luò)的生命周期，提高其能量效率[17]。由于采用分布式的方法，網(wǎng)絡(luò)節(jié)點(diǎn)不能有效地獲取全網(wǎng)節(jié)點(diǎn)在位置、剩余能量、感知范圍、發(fā)射功率等方面的信息，單節(jié)點(diǎn)只能根據(jù)自身以及其相鄰節(jié)點(diǎn)的信息進(jìn)行局部的網(wǎng)絡(luò)控制，網(wǎng)絡(luò)的性能不能達(dá)到全局最優(yōu)。關(guān)于拓?fù)淇刂扑惴ǖ难芯客ǔ；陔S機(jī)圖理論模型[18]，例如基于鄰近圖的功率控制算法等。近年來(lái)已有更多的拓?fù)淠Ｐ捅粦?yīng)用于WSN的拓?fù)淇刂蒲芯恐小Ｈ缥墨I(xiàn)[19]將博弈理論模型應(yīng)用于拓?fù)淇刂蒲芯浚岢隽艘环N非合作式博弈的分布式拓?fù)淇刂品椒ǎ糜趧?dòng)態(tài)設(shè)計(jì)高效和能量均衡的網(wǎng)絡(luò)拓?fù)洌晃墨I(xiàn)[20]提出了一種單純復(fù)形理論應(yīng)用的簡(jiǎn)化算法，用來(lái)刪除網(wǎng)絡(luò)拓?fù)渲卸嘤嗟墓?jié)點(diǎn)，并保持拓?fù)浣Y(jié)構(gòu)的不變性。

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

基于已有軟件定義傳感器網(wǎng)絡(luò)架構(gòu)，本文提出SDSN架構(gòu)，通過(guò)應(yīng)用層中覆蓋優(yōu)化、網(wǎng)絡(luò)的拓?fù)淇刂坪吐酚蓞f(xié)議等相關(guān)應(yīng)用，設(shè)計(jì)網(wǎng)絡(luò)重配置算法，從而完成整個(gè)傳感器網(wǎng)絡(luò)參數(shù)的重新設(shè)置。本文提出一種基于Voronoi圖的動(dòng)態(tài)覆蓋算法，算法中管控中心可以通過(guò)調(diào)節(jié)節(jié)點(diǎn)的感知范圍實(shí)現(xiàn)網(wǎng)絡(luò)的全局覆蓋優(yōu)化，實(shí)現(xiàn)網(wǎng)絡(luò)資源的全局共享；提出一種基于單純復(fù)形理論的拓?fù)淇刂扑惴ǎ谝亚笾木W(wǎng)絡(luò)K重覆蓋的基礎(chǔ)上，借助于SDSN網(wǎng)絡(luò)架構(gòu)的全局信息，算法尋找最簡(jiǎn)練的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，使網(wǎng)絡(luò)性能達(dá)到全局最優(yōu)；提出一種基于多業(yè)務(wù)QoS的路由算法，利用SDSN的控制器獲取整體網(wǎng)絡(luò)的鏈路狀態(tài)和每個(gè)節(jié)點(diǎn)上的能量消耗等信息，在發(fā)生多個(gè)并發(fā)事件時(shí)提高網(wǎng)絡(luò)路由重配置的準(zhǔn)確性和實(shí)時(shí)性。上述算法有機(jī)結(jié)合并通過(guò)軟件定義實(shí)現(xiàn)無(wú)線傳感器網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)和資源的重配置，從而有效提高其性價(jià)比并拓展應(yīng)用領(lǐng)域。

3 軟件定義傳感器網(wǎng)絡(luò)架構(gòu)模型

圖1 SDSN體系架構(gòu)

為了和SDN基本架構(gòu)一致，本文提出的SDSN體系架構(gòu)主體上也分為基礎(chǔ)設(shè)施層、控制層和應(yīng)用層3層。由圖1可見(jiàn)，所提架構(gòu)實(shí)質(zhì)上是由大量軟件定義傳感器節(jié)點(diǎn)和集中式管控中心2部分構(gòu)成，其節(jié)點(diǎn)結(jié)構(gòu)由傳感器模塊和通用可編程數(shù)據(jù)收發(fā)單元組成，其網(wǎng)絡(luò)覆蓋、拓?fù)淇刂啤⒙酚蓞f(xié)議等網(wǎng)絡(luò)控制技術(shù)由集中式管控中心統(tǒng)一配置，并將相應(yīng)配置文件分發(fā)到各節(jié)點(diǎn)的數(shù)據(jù)收發(fā)單元，以獲得全局最優(yōu)的網(wǎng)絡(luò)性能。這一架構(gòu)的主要特點(diǎn)在于可根據(jù)用戶和網(wǎng)絡(luò)狀態(tài)需求，利用可編程控制的網(wǎng)絡(luò)單元，定制算法、策略、協(xié)議等內(nèi)核可高度重構(gòu)化的網(wǎng)絡(luò)支撐系統(tǒng)，通過(guò)OpenFlow等相關(guān)協(xié)議開(kāi)發(fā)面向?qū)ο蟮拈_(kāi)放式管理與業(yè)務(wù)適配接口，實(shí)現(xiàn)軟件定義傳感網(wǎng)信息的抽象化和跨層網(wǎng)絡(luò)控制集成化，從而建立起具備統(tǒng)一網(wǎng)絡(luò)控制能力的適應(yīng)集中控制、節(jié)點(diǎn)網(wǎng)絡(luò)單元簡(jiǎn)化、網(wǎng)絡(luò)管理高效、性能全局最優(yōu)等特點(diǎn)的新型傳感器網(wǎng)絡(luò)架構(gòu)體系，即該架構(gòu)的每一層均服務(wù)于傳感器網(wǎng)絡(luò)的重配置，也可以說(shuō)在每一層中都增加了網(wǎng)絡(luò)重配置單元并且用軟件來(lái)實(shí)現(xiàn)。

在網(wǎng)絡(luò)部署完畢后，管控中心通過(guò)實(shí)時(shí)配置各感知節(jié)點(diǎn)的感知范圍，使監(jiān)測(cè)區(qū)域被SDSN感知并實(shí)現(xiàn)全覆蓋。

4 SDSN的網(wǎng)絡(luò)重配置算法

如前所述，采用所提的SDSN架構(gòu)及其網(wǎng)絡(luò)重配置算法來(lái)解決傳感器網(wǎng)絡(luò)的覆蓋優(yōu)化、拓?fù)淇刂坪吐酚蓛?yōu)化等問(wèn)題，SDSN網(wǎng)絡(luò)重配置算法由基于Voronoi圖的動(dòng)態(tài)覆蓋算法、基于單純復(fù)形理論的拓?fù)淇刂扑惴ê突诙鄻I(yè)務(wù) QoS的路由算法所構(gòu)成，它們有機(jī)結(jié)合，共同完成網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)以及資源的重配置。

4.1 基于Voronoi圖的動(dòng)態(tài)覆蓋算法

SDSN的網(wǎng)絡(luò)拓?fù)渫ǔＪ莿?dòng)態(tài)變化的，當(dāng)有節(jié)點(diǎn)產(chǎn)生移動(dòng)或失效時(shí)，網(wǎng)絡(luò)中各節(jié)點(diǎn)的感知范圍需進(jìn)行調(diào)整以達(dá)到對(duì)監(jiān)測(cè)區(qū)域的完全感知覆蓋；同時(shí)，若網(wǎng)絡(luò)中某一區(qū)域產(chǎn)生突發(fā)事件，相關(guān)聯(lián)的節(jié)點(diǎn)也應(yīng)實(shí)時(shí)調(diào)整自己的感知范圍，以增加對(duì)該區(qū)域的感知精度，實(shí)現(xiàn)對(duì)突發(fā)事件的協(xié)同感知。本文針對(duì)SDSN網(wǎng)絡(luò)重配置算法中的覆蓋需求，提出一種基于Voronoi圖的動(dòng)態(tài)覆蓋方法，通過(guò)引入Voronoi圖理論將監(jiān)測(cè)區(qū)域進(jìn)行凸域劃分，并綜合考慮網(wǎng)絡(luò)的能量均衡和覆蓋冗余，尋求一種最優(yōu)化的節(jié)點(diǎn)感知半徑重配置方案，來(lái)解決網(wǎng)絡(luò)部署或網(wǎng)絡(luò)拓?fù)渥兓瘯r(shí)對(duì)監(jiān)測(cè)區(qū)域的感知全覆蓋問(wèn)題，以及網(wǎng)絡(luò)中發(fā)生突發(fā)事件時(shí)對(duì)目標(biāo)事件區(qū)域進(jìn)行多點(diǎn)協(xié)同感知、實(shí)現(xiàn)K重覆蓋的問(wèn)題。

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

基于 Voronoi圖的動(dòng)態(tài)覆蓋算法的執(zhí)行過(guò)程如圖 2所示，算法通過(guò)實(shí)時(shí)監(jiān)測(cè)網(wǎng)絡(luò)的全局信息，將SDSN的覆蓋優(yōu)化問(wèn)題分為：1）通過(guò)對(duì)區(qū)域的Voronoi劃分和構(gòu)建Delaunay三角剖分，尋求區(qū)域全覆蓋問(wèn)題中保證能量均衡的節(jié)點(diǎn)感知半徑最優(yōu)化配置；2）通過(guò)Voronoi圖和多目標(biāo)決策，選擇最優(yōu)的節(jié)點(diǎn)子集并調(diào)整其感知半徑，求解突發(fā)事件區(qū)域 K重覆蓋問(wèn)題的2個(gè)子問(wèn)題。具體方法如下。

圖2 SDSN中基于Voronoi圖的動(dòng)態(tài)覆蓋算法執(zhí)行過(guò)程

1) 最優(yōu)化感知半徑配置策略

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

一般認(rèn)為在覆蓋問(wèn)題中，節(jié)點(diǎn)的感知行為是能量消耗的主要因素，將節(jié)點(diǎn)si的能耗建模為感知半徑Ri的函數(shù)Pi(Ri)，引入節(jié)點(diǎn)的剩余能量Ei，則整個(gè)網(wǎng)絡(luò)的剩余生命期可以表示為

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

2) 最優(yōu)化節(jié)點(diǎn)子集決策策略

采用覆蓋重?cái)?shù)作為區(qū)域覆蓋的性能指標(biāo)。假設(shè)突發(fā)事件發(fā)生時(shí)，感知節(jié)點(diǎn)sn首先上報(bào)事件信息，則將sn感知范圍作為目標(biāo)區(qū)域Z，sn在Voronoi圖中的M跳鄰居節(jié)點(diǎn)作為候選節(jié)點(diǎn)集Sm={s1,…, sl}，目標(biāo)區(qū)域的覆蓋重?cái)?shù)可以表示為

對(duì)任意 sm∈SM，調(diào)整其感知半徑使其中，是調(diào)整后的半徑，則調(diào)整后的節(jié)點(diǎn)sm可以實(shí)現(xiàn)對(duì)目標(biāo)區(qū)域的覆蓋。管控中心綜合考慮候選節(jié)點(diǎn)調(diào)整半徑所付出的代價(jià)包括網(wǎng)絡(luò)生命期的變化及覆蓋冗余度的增加，從候選集中決策選擇最優(yōu)的K-1個(gè)節(jié)點(diǎn)，調(diào)整其感知半徑以實(shí)現(xiàn)對(duì)目標(biāo)事件區(qū)域的K重覆蓋。式(1)給出

了網(wǎng)絡(luò)的剩余生命期模型，它與節(jié)點(diǎn)的剩余能量 Em和能耗相關(guān)，而覆蓋冗余度的變化量在監(jiān)測(cè)區(qū)域已實(shí)現(xiàn)全覆蓋的情況下可以表示為這樣算法可以建立相應(yīng)的決策代價(jià)函數(shù) H(L,U)進(jìn)行子集決策，決策過(guò)程可以抽象為如下帶約束條件的優(yōu)化模型。

目標(biāo)函數(shù)

約束條件

圖3 SDSN覆蓋優(yōu)化算法的Voronoi模型

通過(guò)對(duì)該優(yōu)化模型的求解分析，可以尋求最優(yōu)的節(jié)點(diǎn)子集和半徑調(diào)整方案，如果候選節(jié)點(diǎn)集較大，可以考慮采用啟發(fā)式算法進(jìn)行子集搜索，以獲得問(wèn)題的次優(yōu)解。

4.2 基于單純復(fù)形理論的拓?fù)淇刂扑惴?/h3>

SDSN網(wǎng)絡(luò)中的傳感器節(jié)點(diǎn)和節(jié)點(diǎn)間通信鏈路可以抽象為0-單形和1-單形，通過(guò)合理地增加或者刪除節(jié)點(diǎn)間的無(wú)線通信鏈路，生成一個(gè)能量高效的優(yōu)化網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)。為了獲取SDSN網(wǎng)絡(luò)連通性的相關(guān)信息，引入單純鏈復(fù)形和貝蒂數(shù)的定義。給定一個(gè)單復(fù)形，它的j維單純鏈Dj是由其j維定向單形生成的拓?fù)淇臻g。單純鏈Dj對(duì)應(yīng)的邊緣算子?j的定義如下

其中，vi表示所對(duì)應(yīng)單形的頂點(diǎn)。應(yīng)用邊緣算子?j可以對(duì)單純復(fù)形的j維單純鏈進(jìn)行降維，從而得到單純復(fù)形的單純鏈復(fù)形

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

其中，dimZj表示 j維閉鏈群 Zj的維數(shù)，dimBj表示 j維邊緣鏈群 Bj的維數(shù)，j-貝蒂數(shù) Bj等于 j維閉鏈群 Zj維數(shù)與 j維邊緣鏈群 Bj維數(shù)的差。在SDSN場(chǎng)景下，0維閉鏈群 Z0的維數(shù)就是 SDSN中傳感器節(jié)點(diǎn)的數(shù)量，0維邊緣鏈群B0的維數(shù)就是全網(wǎng)各連通分量最小連通子集的1-單形數(shù)量之和，從而0-貝蒂數(shù)0β表示SDSN中連通分量的個(gè)數(shù)，1-貝蒂數(shù)則表示二維平面上沒(méi)有無(wú)線信號(hào)覆蓋的空洞的個(gè)數(shù)。

基于上述定義，本算法提出了基于邊緣鏈群最小生成元和節(jié)點(diǎn)度，以最簡(jiǎn)練的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)為目標(biāo)，同時(shí)保證整個(gè)系統(tǒng)的連通性以及突發(fā)區(qū)域頑健性的全局節(jié)點(diǎn)功率最優(yōu)的問(wèn)題，并將該最優(yōu)問(wèn)題分解為幾個(gè)子問(wèn)題進(jìn)行求解，由2個(gè)子過(guò)程來(lái)執(zhí)行，即功率預(yù)配置過(guò)程和功率重配置過(guò)程。功率預(yù)配置過(guò)程確保了網(wǎng)絡(luò)部署和網(wǎng)絡(luò)結(jié)構(gòu)發(fā)生變化時(shí)網(wǎng)絡(luò)拓?fù)涞木?jiǎn)性和連通性，功率重配置過(guò)程確保了網(wǎng)絡(luò)突發(fā)事件發(fā)生時(shí)突發(fā)區(qū)域網(wǎng)絡(luò)拓?fù)涞念B健性。當(dāng)管控中心檢測(cè)到網(wǎng)絡(luò)拓?fù)浒l(fā)生變化時(shí)執(zhí)行功率預(yù)配置過(guò)程，刪除網(wǎng)絡(luò)中冗余的無(wú)線鏈路同時(shí)確保網(wǎng)絡(luò)的連通性；當(dāng)檢測(cè)到突發(fā)事件發(fā)生時(shí)，由SDSN管控中心執(zhí)行功率重配置過(guò)程，調(diào)整突發(fā)事件產(chǎn)生區(qū)域內(nèi)節(jié)點(diǎn)的無(wú)線發(fā)射功率，增加區(qū)域內(nèi)無(wú)線鏈路的冗余度以提高局部區(qū)域的穩(wěn)定性和頑健性。

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

1) 軟件定義傳感網(wǎng)絡(luò)功率預(yù)配置過(guò)程

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

圖4 軟件定義傳感網(wǎng)絡(luò)功率預(yù)配置擬定流程

2) 軟件定義傳感網(wǎng)絡(luò)功率重配置過(guò)程

在確保整個(gè)網(wǎng)絡(luò)連通性的基礎(chǔ)上，SDSN管控中心根據(jù)突發(fā)事件發(fā)生的位置和范圍得到突發(fā)區(qū)域內(nèi)節(jié)點(diǎn)的位置信息，根據(jù)突發(fā)事件的緊急程度來(lái)確定對(duì)突發(fā)區(qū)域內(nèi)節(jié)點(diǎn)度的平均增加量。然后，以區(qū)域外節(jié)點(diǎn)度的變化最小為目標(biāo)對(duì)突發(fā)區(qū)域內(nèi)節(jié)點(diǎn)的發(fā)射功率進(jìn)行迭代調(diào)整，同時(shí)確保每個(gè)迭代步區(qū)域內(nèi)節(jié)點(diǎn)平均度的增量都是一樣的，經(jīng)過(guò)多次迭代可以得到最優(yōu)的重配置節(jié)點(diǎn)集以及相應(yīng)的重配置功率。軟件定義傳感網(wǎng)絡(luò)功率重配置過(guò)程如圖 5所示。

圖5 軟件定義傳感網(wǎng)絡(luò)功率重配置擬定流程

4.3 基于多業(yè)務(wù)QoS的路由算法

在SDSN中，源節(jié)點(diǎn)到目的節(jié)點(diǎn)的路由選擇對(duì)于整個(gè)無(wú)線傳感器網(wǎng)絡(luò)系統(tǒng)的性能具有重要作用。在發(fā)生多個(gè)并發(fā)事件時(shí)，系統(tǒng)中央控制器會(huì)根據(jù)各自源節(jié)點(diǎn)自身業(yè)務(wù)的QoS，整體網(wǎng)絡(luò)的鏈路狀態(tài)和每個(gè)節(jié)點(diǎn)上的能量消耗等信息選擇到目的節(jié)點(diǎn)的路由，提高因突發(fā)事件網(wǎng)絡(luò)中路由重新配置的準(zhǔn)確性和實(shí)時(shí)性。

圖 6是基于多業(yè)務(wù) QoS的路由算法擬定系統(tǒng)，當(dāng)有突發(fā)事件發(fā)生時(shí)，SDSN管控中心接收到源節(jié)點(diǎn)發(fā)起數(shù)據(jù)的發(fā)送請(qǐng)求，管控中心根據(jù)新的突發(fā)事件Unew以及SDSN中剩余正在進(jìn)行的業(yè)務(wù)集Un′ow進(jìn)行合并形成新的業(yè)務(wù)集合 Unow= Un′ow∪ Unew。每個(gè)業(yè)務(wù)集合中的元素包含該業(yè)務(wù)數(shù)據(jù)的發(fā)送端、數(shù)據(jù)的到達(dá)端和數(shù)據(jù)發(fā)送的QoS需求等網(wǎng)絡(luò)信息，新的業(yè)務(wù)集合存儲(chǔ)在管控中心中用于路由計(jì)算。

隨后，根據(jù)新的業(yè)務(wù)集合Unow管控中心集中調(diào)取網(wǎng)絡(luò)中的有效信息用于路由計(jì)算，如各節(jié)點(diǎn)剩余能量E={E1,…,EN}和各個(gè)業(yè)務(wù)的QoS需求等。考慮到節(jié)點(diǎn)的可擴(kuò)展性，多個(gè)無(wú)線收發(fā)裝置同時(shí)配置在一個(gè)傳感器節(jié)點(diǎn)成為可能，因此，基于 SDN的傳感器網(wǎng)路由算法將收發(fā)裝置的可擴(kuò)展性加入路由算法中。由于一個(gè)無(wú)線傳感器節(jié)點(diǎn)可同時(shí)收、同時(shí)發(fā)或者部分收和部分發(fā)送數(shù)據(jù)，因此，不同于傳統(tǒng)單一收發(fā)裝置傳感器網(wǎng)絡(luò)的路由計(jì)算，整個(gè)網(wǎng)絡(luò)的路由將變得極其復(fù)雜。所以，本文將多收發(fā)裝置作為研究路由算法的一個(gè)網(wǎng)絡(luò)特性，同時(shí)可以看到該算法能夠退化到單一收發(fā)裝置的傳感器網(wǎng)絡(luò)中，具有一定的普適作用。業(yè)務(wù)QoS作為衡量該業(yè)務(wù)服務(wù)質(zhì)量的標(biāo)準(zhǔn)有著較好的作用，QoS的關(guān)鍵指標(biāo)主要包括：可用性、吞吐量、時(shí)延、時(shí)延變化和丟失等。本文將考慮網(wǎng)絡(luò)單位時(shí)間內(nèi)傳輸?shù)男畔⒘孔鳛闃I(yè)務(wù)QoS的度量準(zhǔn)則。路由算法依據(jù)業(yè)務(wù)集中每個(gè)業(yè)務(wù)QoS需求動(dòng)態(tài)分配路由給各個(gè)業(yè)務(wù)，保證最大化每個(gè)業(yè)務(wù)的QoS。

圖6 基于多業(yè)務(wù)QoS的路由算法擬定系統(tǒng)

考慮到節(jié)點(diǎn)的可擴(kuò)展性，假設(shè)每個(gè)節(jié)點(diǎn)可以部署一個(gè)或者多個(gè)無(wú)線收發(fā)裝置（異構(gòu)無(wú)線傳感器網(wǎng)絡(luò)中的高級(jí)節(jié)點(diǎn)），同時(shí)整個(gè)網(wǎng)絡(luò)配置K個(gè)正交子信道來(lái)進(jìn)行數(shù)據(jù)的傳送。假設(shè)網(wǎng)絡(luò)中共有N個(gè)節(jié)點(diǎn)，每個(gè)節(jié)點(diǎn)可擁有rn個(gè)無(wú)線收發(fā)裝置，節(jié)點(diǎn)i所擁有的有效傳輸半徑為T(mén)i，節(jié)點(diǎn)i與節(jié)點(diǎn)j的歐氏距離記為dij，由此可得網(wǎng)絡(luò)中可進(jìn)行一跳傳輸?shù)逆溌芳嫌洖?ε= {(i, j)|dij≤ Ti,1 ≤ i, j≤ N, i ≠j} 。

考慮到SDSN干擾受限的特點(diǎn)，同一信道可以在相互獨(dú)立的鏈路上同時(shí)發(fā)送數(shù)據(jù)，又因?yàn)樵诒疚闹蠯個(gè)正交子信道都可以用來(lái)傳輸數(shù)據(jù)。因此，可以得到一個(gè)并發(fā)數(shù)據(jù)傳輸鏈路集，記為P = [1,… , p, … ,|P|]。從而可以調(diào)度每個(gè)并發(fā)鏈路集所占用的時(shí)間百分比，進(jìn)而得到每個(gè)鏈路上單位時(shí)間內(nèi)所能傳送信息量的上限。根據(jù)該信息量上限，可以得到最優(yōu)傳輸路徑。

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

則， vk,p為0；② 若節(jié)點(diǎn)i在并發(fā)鏈路集p上被激

i, j

活且占用子信道k，則 xn

k,p為1，否則，為0。因?yàn)橐粋€(gè)節(jié)點(diǎn)在同一時(shí)刻最多只能與一個(gè)相鄰節(jié)點(diǎn)在某一子信道上進(jìn)行通信，由此可得

因?yàn)槊總€(gè)節(jié)點(diǎn)受到其自身無(wú)線收發(fā)裝置個(gè)數(shù)的限制，由此可以得到

如果2條鏈路可在同一子信道上同時(shí)傳輸，那么這2條鏈路必須相互獨(dú)立，此時(shí)應(yīng)滿足

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

為描述簡(jiǎn)單，歸一化激活鏈路在一個(gè)子信道上的數(shù)據(jù)速率為單位常量，因此，可以得到每條鏈路在單位時(shí)間內(nèi)的信息量上限為

其中，λp為并發(fā)傳輸集合p所占用單位時(shí)間上的百分比數(shù)。

假設(shè)系統(tǒng)有M個(gè)端到端的業(yè)務(wù)流，則每個(gè)業(yè)務(wù)的源節(jié)點(diǎn)、目的節(jié)點(diǎn)和該業(yè)務(wù) QoS可以寫(xiě)為Sm=(sm,dm,Im),sm,dm=1,2,… ,N, Im> 0,m =1,2,… , M 。定義 Iim,j為業(yè)務(wù) m在單位時(shí)間內(nèi)通過(guò)鏈路(i,j)的信息量。

在無(wú)線通信網(wǎng)絡(luò)中，每個(gè)節(jié)點(diǎn)在發(fā)送或接收每個(gè)比特都應(yīng)消耗一定的能量。若節(jié)點(diǎn)發(fā)送ψbit數(shù)據(jù)，則其消耗能量為 ET= Eψ+ αd2ψ；若節(jié)點(diǎn)接

elec

收ψbit數(shù)據(jù)，則其消耗能量為 ER=Eψ。因此，

elec

在單位時(shí)間內(nèi)節(jié)點(diǎn)i發(fā)送數(shù)據(jù)所消耗的能量為

同理，可得在單位時(shí)間內(nèi)節(jié)點(diǎn)i接收數(shù)據(jù)所消耗的能量為

在單位時(shí)間內(nèi)，節(jié)點(diǎn)i所消耗的總能量為

用iρ表示節(jié)點(diǎn)i的能量負(fù)載情況為

其中，Ei為節(jié)點(diǎn)i剩余總能量，E為每個(gè)節(jié)點(diǎn)初始化能量。利用Jain公平指數(shù)，可得

在節(jié)點(diǎn)擁有一個(gè)或者多個(gè)無(wú)線收發(fā)裝置，即節(jié)點(diǎn)間可采用多個(gè)正交子信道進(jìn)行通信和多種業(yè)務(wù)流同時(shí)傳送的場(chǎng)景下，通過(guò)平衡每個(gè)節(jié)點(diǎn)的剩余能量在保證每個(gè)業(yè)務(wù) QoS的前提下延長(zhǎng)網(wǎng)絡(luò)的工作壽命。

該算法可以表述如下。

目標(biāo)函數(shù)

約束條件

目標(biāo)函數(shù)（17）表示最大化網(wǎng)絡(luò)能量Jain公平指數(shù)，以達(dá)到網(wǎng)絡(luò)各節(jié)點(diǎn)剩余能量均衡；約束條件（18）表示在單位時(shí)間內(nèi)m業(yè)務(wù)中流入和流出轉(zhuǎn)發(fā)節(jié)點(diǎn)的信息量應(yīng)相等；約束條件（19）和（20）分別表示在單位時(shí)間內(nèi)屬于 m業(yè)務(wù)的源節(jié)點(diǎn)流入和目的節(jié)點(diǎn)沒(méi)有相應(yīng)信息量流出；約束條件（21）表示單位時(shí)間內(nèi)m業(yè)務(wù)源節(jié)點(diǎn)流出的總信息量；約束條件（22）表示單位時(shí)間內(nèi)所有業(yè)務(wù)在每個(gè)鏈路上的信息量應(yīng)小于該鏈路的單位時(shí)間內(nèi)信息量的上限；約束條件（23）表示每個(gè)節(jié)點(diǎn)上無(wú)線收發(fā)裝置個(gè)數(shù)的約束。

基于多業(yè)務(wù)QoS的路由算法執(zhí)行過(guò)程如圖7所示。當(dāng)網(wǎng)絡(luò)中有突發(fā)事件發(fā)生時(shí)，開(kāi)始路由計(jì)算，管控中心搜集所需信息，依據(jù)非線性有約束規(guī)劃算法進(jìn)行迭代求解，若解滿足收斂條件，則算法終止，若不滿足算法收斂條件，算法繼續(xù)；而當(dāng)網(wǎng)絡(luò)中沒(méi)有突發(fā)事件發(fā)生時(shí)，系統(tǒng)則直接跳過(guò)路由計(jì)算，保持原路由不變。

5 路由算法性能仿真及其結(jié)果分析

為了驗(yàn)證所提網(wǎng)絡(luò)重配置算法，本節(jié)以路由算法為例進(jìn)行性能仿真并分析其結(jié)果，其他算法的仿真及其與已有算法的比較將另文給出。

5.1 仿真場(chǎng)景

圖8給出了本文所提SDSN的工作場(chǎng)景，其初始場(chǎng)景如圖8（a）所示。管控中心對(duì)SDSN節(jié)點(diǎn)剩余能量進(jìn)行衡量，選擇了節(jié)點(diǎn) a、b、c成為接入節(jié)點(diǎn)，剩下的SDSN節(jié)點(diǎn)d、e退化為普通節(jié)點(diǎn)，與區(qū)域內(nèi)其他傳感器節(jié)點(diǎn)一同工作。網(wǎng)絡(luò)中存在若干業(yè)務(wù)，在管控中心的集中式調(diào)度下，它們分別從各自的源節(jié)點(diǎn)到達(dá)目的節(jié)點(diǎn)，系統(tǒng)處于穩(wěn)定的工作狀態(tài)。

隨著突發(fā)事件A的到來(lái)，大量的數(shù)據(jù)需要上傳至管控中心，網(wǎng)絡(luò)中原有的路由已經(jīng)不能滿足新的傳輸需求，管控中心需要對(duì)網(wǎng)絡(luò)中的路由進(jìn)行優(yōu)化，重新選擇接入節(jié)點(diǎn)，并對(duì)接入節(jié)點(diǎn)的發(fā)射功率、路由進(jìn)行重配置，盡可能將系統(tǒng)中的業(yè)務(wù)數(shù)據(jù)上傳，調(diào)整后的系統(tǒng)場(chǎng)景如圖8（b）所示。

仿真采用Matlab，仿真環(huán)境設(shè)置參數(shù)如表1所示。

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

圖7 基于多業(yè)務(wù)QoS的路由算法擬執(zhí)行過(guò)程

圖8 SDSN工作場(chǎng)景

表1 仿真參數(shù)

5.2 仿真結(jié)果及其分析

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

圖9 接入節(jié)點(diǎn)速率收斂曲線

圖10給出接入節(jié)點(diǎn)功率上限與流速率關(guān)系的仿真結(jié)果。由圖可見(jiàn)，接入節(jié)點(diǎn)發(fā)射功率上限從=[1.4 1.4 1.4 1.4]TmW到=[2.6 2.6 2.6 2.6]TmW變化時(shí)，管控中心為各接入節(jié)點(diǎn)分配的最優(yōu)流速率的變化情況，可以發(fā)現(xiàn)，隨著接入節(jié)點(diǎn)最大發(fā)射功率的增大，最優(yōu)流速率也逐漸增大，系統(tǒng)的總吞吐量將隨之增加，表明管控中心能夠充分地對(duì)網(wǎng)絡(luò)中的資源加以調(diào)配，滿足區(qū)域內(nèi)各業(yè)務(wù)數(shù)據(jù)上傳需求，盡可能地提高系統(tǒng)性能。此外，當(dāng)接入節(jié)點(diǎn)最大發(fā)射功率相同時(shí)，管控中心為各接入節(jié)點(diǎn)分配的資源相差不大，表明系統(tǒng)能夠通過(guò)設(shè)置節(jié)點(diǎn)發(fā)射功率的上限有效地均衡系統(tǒng)中接入節(jié)點(diǎn)的能耗，以延長(zhǎng)網(wǎng)絡(luò)的生命周期。

圖10 接入節(jié)點(diǎn)功率上限與流速率關(guān)系曲線

6 結(jié)束語(yǔ)

本文將軟件定義網(wǎng)絡(luò)技術(shù)融合進(jìn)無(wú)線傳感器網(wǎng)絡(luò)，給出了軟件定義傳感器網(wǎng)絡(luò)的體系架構(gòu)，提出了SDSN的網(wǎng)絡(luò)重配置算法，具體包括覆蓋優(yōu)化、拓?fù)淇刂埔约奥酚蓛?yōu)化3個(gè)方面。對(duì)于覆蓋優(yōu)化，提出了一種基于Voronoi圖的動(dòng)態(tài)覆蓋算法，尋求SDSN全覆蓋問(wèn)題中保證網(wǎng)絡(luò)能量均衡的最優(yōu)感知半徑分配，并選擇最優(yōu)節(jié)點(diǎn)子集和其感知半徑，以達(dá)到目標(biāo)區(qū)域的K-覆蓋；在拓?fù)淇刂品矫妫趩渭儚?fù)形理論，提出了一種基于邊緣鏈群最小生成元和節(jié)點(diǎn)度的集中控制方法，包括SDSN功率預(yù)配置過(guò)程中的邊緣鏈群最小生成元高效、次優(yōu)算法，以及快速、高效的SDSN功率重配置迭代算法，保證了整個(gè)系統(tǒng)的連通性以及突發(fā)區(qū)域的頑健性；考慮SDSN中路由協(xié)議的自適應(yīng)性以及其在動(dòng)態(tài)環(huán)境下的性能，提出一種基于多業(yè)務(wù)QoS的SDSN路由優(yōu)化算法，依據(jù)每個(gè)業(yè)務(wù)的QoS需求動(dòng)態(tài)分配路由，從而保證多個(gè)業(yè)務(wù)同時(shí)進(jìn)行數(shù)據(jù)傳遞以及各自QoS的最大化，同時(shí)平衡傳感器節(jié)點(diǎn)的剩余能量。以路由算法為例進(jìn)行了仿真，結(jié)果表明所提路由算法能夠有效分配資源，滿足SDSN網(wǎng)絡(luò)中多業(yè)務(wù)QoS需求并延長(zhǎng)網(wǎng)絡(luò)的生命周期。

7 致謝

東南大學(xué)移動(dòng)通信國(guó)家重點(diǎn)實(shí)驗(yàn)室博士生張瑞、劉誠(chéng)毅、茆意偉、章躍躍參與了本文初稿的部分撰寫(xiě)，碩士生李媚、丁翠、曹智勇、唐敏等對(duì)本文所提算法研制了實(shí)驗(yàn)系統(tǒng)并進(jìn)行了仿真，在此一并致謝。

[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] 甘從輝, 鄭國(guó)強(qiáng), 唐盛禹. 無(wú)線傳感器網(wǎng)絡(luò)的拓?fù)淇刂蒲芯縖J]. 計(jì)算機(jī)應(yīng)用研究, 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

國(guó)家自然科學(xué)基金項(xiàng)目資助（No.61471164）；東南大學(xué)移動(dòng)通信國(guó)家重點(diǎn)實(shí)驗(yàn)室自主研究基金資助項(xiàng)目（No.2016B02）

沈連豐（1952-），男，江蘇邳州人，東南大學(xué)教授、博士生導(dǎo)師，主要研究方向?yàn)閷拵б苿?dòng)通信、短距離無(wú)線通信和泛在網(wǎng)絡(luò)等。

朱亞萍（1990-），女，江蘇建湖人，東南大學(xué)博士生，主要研究方向?yàn)閷拵б苿?dòng)通信、無(wú)線傳感器網(wǎng)絡(luò)定位等。

丁兆明（1978-），男，山東日照人，東南大學(xué)博士生，主要研究方向?yàn)闊o(wú)線傳感器網(wǎng)絡(luò)、拓?fù)淇刂频取?/p>

燕鋒（1983-），男，湖北天門(mén)人，博士，東南大學(xué)副研究員，主要研究方向?yàn)闊o(wú)線傳感器網(wǎng)絡(luò)、異構(gòu)網(wǎng)絡(luò)等。

鄧曙光（1972-），男，湖南益陽(yáng)人，博士，湖南城市學(xué)院教授，主要研究方向?yàn)闊o(wú)線傳感器網(wǎng)絡(luò)、車(chē)域網(wǎng)、異構(gòu)網(wǎng)絡(luò)等。