基于軟件定義的WSNs非均勻分簇QoS路由算法*

茍平章，原 晨，張 芬

(西北師范大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院，甘肅 蘭州 730070)

1 引言

隨著無(wú)線傳感器網(wǎng)絡(luò)WSNs(Wireless Sensor Networks)[1]的普及，其數(shù)據(jù)類(lèi)型逐步多樣化，應(yīng)用場(chǎng)景逐步增多，網(wǎng)絡(luò)對(duì)路由協(xié)議服務(wù)質(zhì)量QoS(Quality of Service)[2]的要求也逐漸提高。但是，傳統(tǒng)WSNs的局限性使得QoS路由也面臨諸多問(wèn)題，如節(jié)點(diǎn)能量受限的特性使得節(jié)點(diǎn)無(wú)法進(jìn)行大量復(fù)雜的QoS指標(biāo)參數(shù)計(jì)算；節(jié)點(diǎn)處理數(shù)據(jù)的能力和存儲(chǔ)空間有限，導(dǎo)致網(wǎng)絡(luò)QoS無(wú)法進(jìn)一步提高；無(wú)法根據(jù)不同QoS需求實(shí)時(shí)動(dòng)態(tài)地調(diào)整網(wǎng)絡(luò)路由；路由協(xié)議多為分布式，通過(guò)鄰居節(jié)點(diǎn)信息交換來(lái)計(jì)算路徑，導(dǎo)致路由算法僅在局部能得到最優(yōu)結(jié)果，進(jìn)而影響網(wǎng)絡(luò)QoS。因此，如何有效地提高網(wǎng)絡(luò)QoS仍然是一個(gè)具有挑戰(zhàn)性的問(wèn)題。另一方面，在WSNs路由領(lǐng)域中，為提高能量效率，研究人員提出基于分簇原理的層次型路由。LEACH(Low Energy Adaptive Clustering Hierarchy)協(xié)議[3]是最早的分簇路由協(xié)議，能有效降低節(jié)點(diǎn)能耗，延長(zhǎng)網(wǎng)絡(luò)生命周期，但隨機(jī)性的簇頭選舉策略導(dǎo)致節(jié)點(diǎn)能耗不均衡。為緩解能量黑洞的現(xiàn)象，EEUC(Energy-Efficient Uneven Clustering)協(xié)議[4]通過(guò)節(jié)點(diǎn)競(jìng)爭(zhēng)半徑公式將網(wǎng)絡(luò)分為大小不同的簇，平衡各簇頭間的能量消耗，但簇頭算法仍然采取隨機(jī)的方式，導(dǎo)致簇?zé)o法達(dá)到最優(yōu)。CRIPSO(Clustering Routing protocol based on Improved PSO algorithm)[5]通過(guò)優(yōu)化粒子群優(yōu)化算法的慣性系數(shù)和學(xué)習(xí)因子，平衡算法的全局搜索與局部探索能力，選舉出能量和位置合理的簇頭節(jié)點(diǎn)。

軟件定義網(wǎng)絡(luò)SDN (Software Defined Network)[6]是一種新型網(wǎng)絡(luò)架構(gòu)，是網(wǎng)絡(luò)虛擬化的一種實(shí)現(xiàn)方式。SDN通過(guò)分離控制平面和數(shù)據(jù)平面以及開(kāi)放通信協(xié)議，打破了傳統(tǒng)網(wǎng)絡(luò)設(shè)備的封閉性[7]。其整體框架分為應(yīng)用層、控制層和數(shù)據(jù)層，應(yīng)用層包含各種網(wǎng)絡(luò)業(yè)務(wù)，給用戶(hù)提供實(shí)現(xiàn)和部署網(wǎng)絡(luò)應(yīng)用的接口；控制層通過(guò)網(wǎng)絡(luò)狀態(tài)信息，獲取網(wǎng)絡(luò)拓?fù)渑c視圖，制定并下發(fā)數(shù)據(jù)轉(zhuǎn)發(fā)規(guī)則；數(shù)據(jù)層負(fù)責(zé)數(shù)據(jù)的處理、轉(zhuǎn)發(fā)和狀態(tài)的搜集[8]。將SDN與WSNs相結(jié)合，形成的軟件定義無(wú)線傳感器網(wǎng)絡(luò)SDWSN (Software Defined Wireless Sensor Network)將成為下一代WSNs技術(shù)探索的主流方向[9]。Luo等人[10]結(jié)合WSNs應(yīng)用需求，提出基于SDN的Sensor OpenFlow架構(gòu)，旨在對(duì)SDWSN南向接口協(xié)議進(jìn)行標(biāo)準(zhǔn)化，通過(guò)啟用傳感器節(jié)點(diǎn)的可編程性，增強(qiáng)網(wǎng)絡(luò)控制。Gante等人[11]提出一種新型的基于SDN的WSNs基站架構(gòu)，傳感器節(jié)點(diǎn)不必做出路由決策，而由網(wǎng)絡(luò)管理員通過(guò)控制器提供的全網(wǎng)拓?fù)湟晥D做出最佳決策，提高傳輸效率并減少節(jié)點(diǎn)能耗。文獻(xiàn)[12]提出擾動(dòng)粒子群優(yōu)化的SDWSN路由算法tPSOEB (extremum disturbed Particle Swarm Optimization based Energy-Balanced routing protocols)，采用SDN集中式的計(jì)算方式，通過(guò)引入擾動(dòng)改進(jìn)粒子群優(yōu)化算法的搜索性能，進(jìn)行簇頭選舉與非均勻分簇。

隨著SDWSN理論逐漸成熟，針對(duì)網(wǎng)絡(luò)QoS的路由策略也逐漸應(yīng)用其中。文獻(xiàn)[13]提出一種軟件定義的WSNs控制器實(shí)現(xiàn)方式，采用基于模糊邏輯算法和貝葉斯推理的方案，確定WSNs中合適的端到端QoS路徑。Dio等人[14]為了提高網(wǎng)絡(luò)QoS，通過(guò)對(duì)節(jié)點(diǎn)擁塞狀態(tài)和數(shù)據(jù)等級(jí)的劃分設(shè)置不同的丟包率，提升了網(wǎng)絡(luò)性能，但未涉及到路由協(xié)議。為了解決SDWSN中的路由節(jié)能問(wèn)題，文獻(xiàn)[15]提出一種集中式路由算法IA-EERA(Interference-Aware Energy-Efficient Routing Algorithm)，同時(shí)考慮鏈路Q(chēng)oS和負(fù)載平衡問(wèn)題，以延長(zhǎng)網(wǎng)絡(luò)生命周期。文獻(xiàn)[16]提出一種QoS路徑選擇和資源關(guān)聯(lián)方案Q-PSR (QoS Path Selection and Resource-associating)，用于自適應(yīng)負(fù)載平衡和智能資源控制，實(shí)現(xiàn)最佳網(wǎng)絡(luò)性能。

在上述研究基礎(chǔ)上，本文提出一種基于軟件定義的無(wú)線傳感器網(wǎng)絡(luò)非均勻分簇QoS路由算法SDNUCQS(Software-Defined Non-Uniform Clustering QoS routing algorithm)。初始階段，控制器執(zhí)行全網(wǎng)拓?fù)浒l(fā)現(xiàn)及信息收集過(guò)程，建立網(wǎng)絡(luò)拓?fù)鋱D，獲取所需的網(wǎng)絡(luò)信息。分簇階段，控制器以節(jié)點(diǎn)能量、節(jié)點(diǎn)間距離、傳輸時(shí)延和傳輸丟失率為指標(biāo)，采用熵權(quán)法競(jìng)選出針對(duì)QoS的高質(zhì)量簇頭，根據(jù)競(jìng)爭(zhēng)半徑公式將網(wǎng)絡(luò)分成大小不同的簇。簇間路由階段，利用交叉分類(lèi)法將所要傳輸?shù)臄?shù)據(jù)以時(shí)延和丟失率為參數(shù)分為不同種類(lèi)。對(duì)于有QoS需求的數(shù)據(jù)，采用Dijkstra算法計(jì)算最佳路徑；對(duì)于無(wú)QoS需求的普通數(shù)據(jù)，先計(jì)算節(jié)點(diǎn)負(fù)載度，并以此為參數(shù)，采用Dijkstra算法計(jì)算最佳路徑，達(dá)到網(wǎng)絡(luò)負(fù)載均衡的目的。

2 系統(tǒng)模型

2.1 SDWSN體系結(jié)構(gòu)

SDWSN中控制器部署方式有3種，分別為單控制器部署、水平多控制器部署和層次化多控制器部署。本文采用水平多控制器部署方式中的SDN-WISE(Software Defined Networking solution for WIreless SEnsor networks)[17]體系結(jié)構(gòu)實(shí)現(xiàn)WSNs的SDN化。SDN-WISE體系結(jié)構(gòu)如圖1所示。

Figure 1 SDN-WISE architecture 圖1 SDN-WISE體系結(jié)構(gòu)

圖1的SDN-WISE體系中，基于IEEE 802.15.4和MAC(Multiple Access Channel)層構(gòu)建傳感器節(jié)點(diǎn)，Sink節(jié)點(diǎn)與控制器之間設(shè)計(jì)有適配器，用來(lái)格式化傳輸?shù)臄?shù)據(jù)。FWD(ForWarDing)為轉(zhuǎn)發(fā)層，按照WISE流表中的指示處理匹配成功的數(shù)據(jù)包。網(wǎng)內(nèi)數(shù)據(jù)包處理層INPP (In-Network Packet Processing)用于進(jìn)行數(shù)據(jù)融合或處理數(shù)據(jù)包。TD(Topology Discovery)層用來(lái)維護(hù)鄰居節(jié)點(diǎn)列表，輔助控制器進(jìn)行拓?fù)浒l(fā)現(xiàn)?？刂茖又?，WISE-VISOR受控制器管理，用于提取網(wǎng)絡(luò)資源，以便不同管理策略或邏輯網(wǎng)絡(luò)可在同一物理設(shè)備上執(zhí)行?？刂破骱蚖ISE-VISOR共同決定網(wǎng)絡(luò)邏輯。節(jié)點(diǎn)根據(jù)流表匹配結(jié)果進(jìn)行數(shù)據(jù)包轉(zhuǎn)發(fā)。流表由3部分組成：用于數(shù)據(jù)包匹配的匹配域(Matching Rule)、用于統(tǒng)計(jì)匹配數(shù)據(jù)包個(gè)數(shù)的統(tǒng)計(jì)域(Statistics)和用于展示匹配數(shù)據(jù)包處理方式的操作域(Action)。節(jié)點(diǎn)流表圖如圖2所示。

Figure 2 Structure of flow table 圖2 流表結(jié)構(gòu)

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

本文WSNs模型由傳感器控制服務(wù)器、Sink節(jié)點(diǎn)，以及隨機(jī)分布在M×M大小的檢測(cè)區(qū)域中的N個(gè)傳感器節(jié)點(diǎn)組成。相關(guān)網(wǎng)絡(luò)模型約束為：

假設(shè)1所有傳感器節(jié)點(diǎn)隨機(jī)分配在檢測(cè)區(qū)域內(nèi)，并且其位置在整個(gè)生命周期中不會(huì)發(fā)生改變，與Sink節(jié)點(diǎn)和控制器的關(guān)系位置同樣也是固定的。

假設(shè)2所有傳感器節(jié)點(diǎn)具有相同的初始能量，每個(gè)節(jié)點(diǎn)擁有唯一的ID標(biāo)識(shí)，均有機(jī)會(huì)充當(dāng)簇頭。

假設(shè)3節(jié)點(diǎn)的發(fā)射功率能夠根據(jù)傳輸距離自動(dòng)調(diào)整。

假設(shè)4傳感器控制服務(wù)器僅有一個(gè)且能量不做限制。

2.3 能耗模型

能耗模型采用經(jīng)典的無(wú)線傳輸能量消耗模型[18]，如圖3所示，當(dāng)傳輸kbit數(shù)據(jù)時(shí)，發(fā)送端的能耗為傳輸電路消耗和信號(hào)放大電路消耗；接收端能耗為信號(hào)接收電路能耗。

Figure 3 Energy consumption model圖3 能量消耗模型

根據(jù)發(fā)送節(jié)點(diǎn)和接收節(jié)點(diǎn)之間的距離，采用自由空間和多路徑衰減模型，節(jié)點(diǎn)發(fā)送kbit數(shù)據(jù)到距離為d的節(jié)點(diǎn)消耗的能量如式(1)所示：

(1)

其中，Eelec表示接收或發(fā)送數(shù)據(jù)時(shí)的電路功率消耗系數(shù)，εfs為自由空間模型的放大倍數(shù)，εmp為多路徑傳輸模型的放大倍數(shù)，d為節(jié)點(diǎn)間距離,d0為通信距離分界值,其計(jì)算如式(2)所示：

(2)

節(jié)點(diǎn)接收kbit數(shù)據(jù)消耗的能量如式(3)所示：

ERx(k)=kEelec

(3)

3 SDNUCQS路由算法

SDNUCQS算法包括拓?fù)浒l(fā)現(xiàn)階段、簇的形成階段、簇間路由建立和數(shù)據(jù)傳輸4個(gè)階段。拓?fù)浒l(fā)現(xiàn)階段，控制器獲取網(wǎng)絡(luò)拓?fù)鋱D及其他所需信息。簇的形成階段，采用熵權(quán)法，結(jié)合QoS指標(biāo)，競(jìng)選出針對(duì)網(wǎng)絡(luò)QoS的高質(zhì)量簇頭，并進(jìn)行非均勻分簇。簇間路由階段，控制器根據(jù)時(shí)延和丟失率將數(shù)據(jù)分類(lèi)，對(duì)不同數(shù)據(jù)有針對(duì)性地制定最佳傳輸路徑，并下發(fā)流表。數(shù)據(jù)傳輸階段，簇頭收集簇內(nèi)節(jié)點(diǎn)數(shù)據(jù)并按照流表規(guī)則進(jìn)行數(shù)據(jù)傳輸。

3.1 拓?fù)浒l(fā)現(xiàn)及信息收集

在網(wǎng)絡(luò)初始化階段，控制器需要進(jìn)行拓?fù)浒l(fā)現(xiàn)和信息收集流程，其目的在于獲取網(wǎng)絡(luò)數(shù)據(jù)平面拓?fù)鋱D及其他信息(網(wǎng)絡(luò)QoS指標(biāo)、節(jié)點(diǎn)剩余能量)?？刂破魍ㄟ^(guò)Sink節(jié)點(diǎn)下發(fā)拓?fù)浒l(fā)現(xiàn)包(TD)，TD信息包括節(jié)點(diǎn)剩余能量，與Sink節(jié)點(diǎn)間的距離，以及端到端QoS參數(shù)(包括時(shí)延和數(shù)據(jù)丟失率)信息等。

圖4所示為拓?fù)浒l(fā)現(xiàn)過(guò)程，節(jié)點(diǎn)A廣播TD(A)，節(jié)點(diǎn)B接收到TD(A)后，首先將A的剩余能量、QoS參數(shù)等信息保存起來(lái)，并將A加入至其鄰居節(jié)點(diǎn)列表中；其次比較A和B到Sink節(jié)點(diǎn)的跳數(shù)大小，若A到Sink節(jié)點(diǎn)的跳數(shù)大于B的，則B到Sink節(jié)點(diǎn)的跳數(shù)為A的加一，并規(guī)定B到Sink節(jié)點(diǎn)的下一跳為A;最后B廣播TD(B)。通過(guò)此流程直至全網(wǎng)節(jié)點(diǎn)皆完成廣播，將所有數(shù)據(jù)發(fā)送至Sink節(jié)點(diǎn)，最終Sink節(jié)點(diǎn)將數(shù)據(jù)發(fā)送至控制器?？刂破鞯玫綌?shù)據(jù)后，建立全網(wǎng)拓?fù)鋱D并擁有節(jié)點(diǎn)剩余能量、節(jié)點(diǎn)間距離、鄰居節(jié)點(diǎn)列表和QoS參數(shù)。

Figure 4 Process of topology discovery 圖4 拓?fù)浒l(fā)現(xiàn)過(guò)程

3.2 基于熵權(quán)法的簇頭選舉

熵權(quán)法是一種客觀賦權(quán)法，依賴(lài)于數(shù)據(jù)本身的離散程度。傳統(tǒng)分簇路由的簇頭選舉多為多指標(biāo)加權(quán)和的形式，人為確定各數(shù)據(jù)指標(biāo)的權(quán)重大小，使數(shù)據(jù)所占比重缺乏客觀性，導(dǎo)致理論上選舉出的簇頭與實(shí)際最優(yōu)簇頭存在偏差。本文結(jié)合QoS指標(biāo)，采用熵權(quán)法進(jìn)行簇頭選舉，對(duì)數(shù)據(jù)進(jìn)行客觀度量。簇頭選舉流程包括數(shù)據(jù)指標(biāo)分析、節(jié)點(diǎn)評(píng)估、簇頭確定和分簇4個(gè)階段。

3.2.1 數(shù)據(jù)指標(biāo)分析

通過(guò)剩余能量、平均向心距離、平均向心鏈路連通度和平均向心端到端時(shí)延4個(gè)數(shù)據(jù)指標(biāo)對(duì)節(jié)點(diǎn)進(jìn)行評(píng)估。

假設(shè)節(jié)點(diǎn)競(jìng)爭(zhēng)半徑范圍內(nèi)有n個(gè)節(jié)點(diǎn)，而每個(gè)節(jié)點(diǎn)有4個(gè)指標(biāo)，則第i個(gè)節(jié)點(diǎn)的第m個(gè)指標(biāo)可描述為xim(i=1,2,…,n;m=1,2,3,4)。

(1) 節(jié)點(diǎn)剩余能量。剩余能量越高，越容易成為簇頭。設(shè)競(jìng)爭(zhēng)半徑內(nèi)第i個(gè)節(jié)點(diǎn)的剩余能量為xi1=Ere(i)，Ere(i)為第i個(gè)節(jié)點(diǎn)的剩余能量。

(2) 平均向心距離指競(jìng)爭(zhēng)半徑內(nèi)其他節(jié)點(diǎn)與該節(jié)點(diǎn)之間距離的平均值。該值越小，越容易成為簇頭。第i個(gè)節(jié)點(diǎn)的平均向心距離如式(4)所示：

(4)

其中，d(i,j)表示第i個(gè)節(jié)點(diǎn)和第j個(gè)節(jié)點(diǎn)間的距離。

(3) 平均向心鏈路連通度表示競(jìng)爭(zhēng)半徑內(nèi)其他節(jié)點(diǎn)向該節(jié)點(diǎn)傳輸數(shù)據(jù)完整率的平均值。平均值越高，該節(jié)點(diǎn)越容易成為簇頭。競(jìng)爭(zhēng)半徑內(nèi)第i個(gè)節(jié)點(diǎn)的平均向心鏈路連通度如式(5)所示：

(5)

其中，s(j,i)和f(j,i)分別為第j個(gè)節(jié)點(diǎn)向第i個(gè)節(jié)點(diǎn)發(fā)送數(shù)據(jù)包成功到達(dá)的大小和發(fā)送數(shù)據(jù)包的大小。

(4) 平均向心端到端時(shí)延指節(jié)點(diǎn)競(jìng)爭(zhēng)半徑內(nèi)其他節(jié)點(diǎn)向該節(jié)點(diǎn)傳輸數(shù)據(jù)端到端時(shí)延平均值。該值越低，節(jié)點(diǎn)越容易成為簇頭。競(jìng)爭(zhēng)半徑內(nèi)第i個(gè)節(jié)點(diǎn)單位數(shù)據(jù)傳輸時(shí)延如式(6)所示：

(6)

其中，t(j,i)表示第j個(gè)節(jié)點(diǎn)向第i個(gè)節(jié)點(diǎn)發(fā)送1 bit數(shù)據(jù)所用時(shí)間。

3.2.2 節(jié)點(diǎn)評(píng)估

使用熵權(quán)法對(duì)節(jié)點(diǎn)指標(biāo)進(jìn)行計(jì)算，得到節(jié)點(diǎn)綜合實(shí)力。具體步驟如下所示：

步驟1指標(biāo)歸一化處理。指標(biāo)分為正向指標(biāo)和負(fù)向指標(biāo)，正向指標(biāo)數(shù)值越高越好，負(fù)向指標(biāo)數(shù)值越低越好，因此，對(duì)于正向指標(biāo)和負(fù)向指標(biāo)需要采用不同的算法進(jìn)行數(shù)據(jù)標(biāo)準(zhǔn)化處理。

剩余能量和平均向心鏈路連通度是正向指標(biāo)，正向指標(biāo)歸一化公式如式(7)所示：

(7)

平均向心距離和單位數(shù)據(jù)傳輸時(shí)延為負(fù)向指標(biāo)，負(fù)向指標(biāo)歸一化公式如式(8)所示：

(8)

其中，x′im表示經(jīng)過(guò)歸一化處理后第i個(gè)節(jié)點(diǎn)的第m個(gè)指標(biāo)值，xim為第i個(gè)節(jié)點(diǎn)的第m個(gè)指標(biāo)，min(xim)和max(xim)分別為指標(biāo)函數(shù)最小值和最大值。

步驟2計(jì)算各個(gè)指標(biāo)下，每個(gè)樣本的數(shù)據(jù)分析指標(biāo)占總指標(biāo)的比重。競(jìng)爭(zhēng)半徑內(nèi)第i個(gè)節(jié)點(diǎn)的第m個(gè)指標(biāo)所占總指標(biāo)比重如式(9)所示：

i=1,2,…,n;m=1,2,3,4

(9)

步驟3計(jì)算各個(gè)指標(biāo)的熵值。第m項(xiàng)指標(biāo)的熵值如式(10)所示：

(10)

步驟4計(jì)算各指標(biāo)信息熵冗余度,如式(11)所示：

Dm=1-Em,m=1,2,3,4

(11)

步驟5計(jì)算各指標(biāo)的權(quán)重,如式(12)所示：

(12)

步驟6通過(guò)指標(biāo)數(shù)值及權(quán)重，計(jì)算各節(jié)點(diǎn)的綜合實(shí)力S。競(jìng)爭(zhēng)半徑內(nèi)第i個(gè)節(jié)點(diǎn)的綜合實(shí)力Si如式(13)所示：

(13)

3.2.3 簇頭確定及分簇

在SDWSN中分簇流程由控制服務(wù)器完成，極大地節(jié)省了節(jié)點(diǎn)能耗，具體流程如下所示：

步驟1節(jié)點(diǎn)競(jìng)爭(zhēng)半徑的確定。為緩解網(wǎng)絡(luò)“熱區(qū)”問(wèn)題，本文采用文獻(xiàn)[4]的節(jié)點(diǎn)競(jìng)爭(zhēng)半徑計(jì)算公式，如式(14)所示：

(14)

控制器按照式(14)計(jì)算每個(gè)節(jié)點(diǎn)的競(jìng)爭(zhēng)半徑，并為其維護(hù)一個(gè)鄰居列表NL(Neighboor List)，用來(lái)保存競(jìng)爭(zhēng)半徑內(nèi)的節(jié)點(diǎn)ID。

步驟2節(jié)點(diǎn)評(píng)估。控制器通過(guò)上述熵權(quán)法流程依次計(jì)算每個(gè)競(jìng)爭(zhēng)半徑內(nèi)所有節(jié)點(diǎn)的綜合實(shí)力S，并計(jì)算各個(gè)節(jié)點(diǎn)成為簇頭的優(yōu)先級(jí)，如式(15)所示：

(15)

其中，pri(i)表示節(jié)點(diǎn)si的優(yōu)先級(jí)，NLi為節(jié)點(diǎn)si鄰居列表，n(NLi)表示節(jié)點(diǎn)si鄰居節(jié)點(diǎn)個(gè)數(shù)，S(i)表示節(jié)點(diǎn)si通過(guò)熵權(quán)法計(jì)算后的節(jié)點(diǎn)綜合實(shí)力。

步驟3簇頭確定?？刂破鞲鶕?jù)計(jì)算得到的節(jié)點(diǎn)優(yōu)先級(jí)從大到小排序，得到簇頭競(jìng)選列表CHC(Cluster Head Competition list)，并建立簇頭列表CH(Cluster Head list)，依次將CHC中節(jié)點(diǎn)ID放入CH中，每放進(jìn)去一個(gè)，則刪除存在于CHC中的鄰居節(jié)點(diǎn)，直到CHC為空。對(duì)于同時(shí)屬于多個(gè)簇的節(jié)點(diǎn)，則選擇距離最近的簇頭加入該簇，最后所有節(jié)點(diǎn)有且僅有一個(gè)歸屬簇，至此分簇完成。

步驟4下發(fā)分簇規(guī)則。控制器計(jì)算得到簇頭及簇成員集合后，將簇成員信息發(fā)送到對(duì)應(yīng)簇頭，簇頭收到信息后生成對(duì)應(yīng)流表項(xiàng)，并生成簇成員通知信息，發(fā)送到簇內(nèi)各節(jié)點(diǎn)。

3.3 簇間路由

簇間路由階段，根據(jù)時(shí)延和丟失率將數(shù)據(jù)分類(lèi)，控制器針對(duì)不同類(lèi)型數(shù)據(jù)制定路由策略。

3.3.1 數(shù)據(jù)分類(lèi)

利用交叉分類(lèi)法，依據(jù)傳輸時(shí)延和丟失率，將數(shù)據(jù)分為4類(lèi)，如表1所示，其中前3類(lèi)為QoS需求數(shù)據(jù)，第4類(lèi)是普通數(shù)據(jù)。表1中0代表不敏感，1代表敏感。

Table 1 Data classification

3.3.2 有QoS需求數(shù)據(jù)的路由

由表1可知QoS數(shù)據(jù)分為3類(lèi)：時(shí)延敏感型數(shù)據(jù)、丟失率敏感型數(shù)據(jù)、時(shí)延和丟失率均敏感型數(shù)據(jù)。

對(duì)于時(shí)延敏感型數(shù)據(jù)，控制器根據(jù)簇頭信息建立網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，結(jié)合鏈路信息得到每條鏈路的端到端時(shí)延，以時(shí)延為鏈路權(quán)值，通過(guò)Dijkstra算法計(jì)算每個(gè)簇頭節(jié)點(diǎn)到Sink節(jié)點(diǎn)的最佳路徑,如式(16)所示：

rtime(i,e)=argsmin∑r(h,j)∈rs(i,e)T(r(h,j))

(16)

其中，rtime(i,e)表示節(jié)點(diǎn)si到Snik節(jié)點(diǎn)時(shí)延敏感型數(shù)據(jù)傳輸?shù)淖罴崖窂?，rs(i,e)表示節(jié)點(diǎn)si至Sink節(jié)點(diǎn)的路徑集合，r(h,j)表示相鄰節(jié)點(diǎn)sh和sj的路徑，T()表示鏈路時(shí)延。

對(duì)于丟失率敏感型數(shù)據(jù)，控制器同樣建立網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，并得到每條鏈路的傳輸丟失率，但由于丟失率為乘性系數(shù)，應(yīng)先取對(duì)數(shù)后再采用Dijkstra算法計(jì)算路徑，如式(17)所示：

rloss(i,e)=argsmin∑r(h,j)∈rs(i,e)lnL(r(h,j))

(17)

其中，rloss(i,e)表示節(jié)點(diǎn)si至Sink節(jié)點(diǎn)丟失率敏感型數(shù)據(jù)的最佳路徑，L()表示鏈路傳輸丟失率。

對(duì)于時(shí)延和丟失率均敏感型數(shù)據(jù)，為了對(duì)鏈路的時(shí)延和丟失率分配客觀權(quán)重，控制器首先使用熵權(quán)法，以鏈路端到端時(shí)延和傳輸丟失率作為數(shù)據(jù)指標(biāo)，計(jì)算出網(wǎng)絡(luò)中每條鏈路的綜合得分；其次以鏈路得分為度量，采用Dijkstra算法計(jì)算出節(jié)點(diǎn)到達(dá)Sink節(jié)點(diǎn)的最佳路徑。

具體流程如下所示：

步驟1控制器建立有向連通圖，得到全網(wǎng)中簇頭節(jié)點(diǎn)間的b條鏈路，將各鏈路端到端時(shí)延和傳輸丟失率作為數(shù)據(jù)指標(biāo)，設(shè)第a條鏈路的端到端時(shí)延和傳輸丟失率分別表示為xa1和xa2。

步驟2對(duì)指標(biāo)進(jìn)行歸一化處理。時(shí)延和丟失率均為負(fù)向指標(biāo)，使用式(9)處理指標(biāo)數(shù)據(jù)。設(shè)歸一化后，第a條鏈路的時(shí)延和丟失率分別為x′a1和x′a2。

步驟3通過(guò)熵權(quán)法計(jì)算，第a條鏈路綜合得分通過(guò)式(18)計(jì)算得到，綜合得分越高，鏈路越適合傳輸數(shù)據(jù)。

SCa=x′a1W1+x′a2W2,a=1,2,…,b

(18)

其中，W1表示熵權(quán)法計(jì)算出的時(shí)延權(quán)重，W2表示丟失率權(quán)重。

為了表達(dá)清晰，將式(18)重新定義為節(jié)點(diǎn)sz向節(jié)點(diǎn)su傳輸數(shù)據(jù)的鏈路得分：

SC(z,u)=W1t(z,u)+W2l(z,u)

(19)

其中，t(z,u)和l(z,u)分別表示歸一化處理后節(jié)點(diǎn)sz和su之間的鏈路時(shí)延和丟失率指標(biāo)值。

步驟4路徑計(jì)算。因?yàn)殒溌返梅衷礁撸竭m合作為傳輸路徑，因此控制器以鏈路得分的倒數(shù)為度量，采用Dijkstra算法計(jì)算，路徑公式如式(20)所示：

(20)

其中，rQoS(i,e)表示對(duì)時(shí)延和丟失率均敏感型數(shù)據(jù)的節(jié)點(diǎn)si至Sink節(jié)點(diǎn)的最佳路徑，p(i,e)表示節(jié)點(diǎn)si和Sink節(jié)點(diǎn)間路徑上的節(jié)點(diǎn)集合，SC(z,u)表示相鄰節(jié)點(diǎn)sz和su的鏈路得分。

3.3.3 無(wú)QoS需求普通數(shù)據(jù)的路由

對(duì)于無(wú)QoS需求的普通節(jié)點(diǎn)，為了使全網(wǎng)節(jié)點(diǎn)能耗均衡，延長(zhǎng)網(wǎng)絡(luò)生命周期，通過(guò)式(21)計(jì)算節(jié)點(diǎn)負(fù)載度。節(jié)點(diǎn)負(fù)載度表示數(shù)據(jù)傳輸時(shí)接收節(jié)點(diǎn)相對(duì)于發(fā)送節(jié)點(diǎn)的工作負(fù)載大小，負(fù)載越大，則該接收節(jié)點(diǎn)越不適合作為下一跳節(jié)點(diǎn)。

(21)

其中，Cj(o)為節(jié)點(diǎn)sj相對(duì)于節(jié)點(diǎn)so的節(jié)點(diǎn)負(fù)載度；d(o,j)為節(jié)點(diǎn)so與節(jié)點(diǎn)sj之間的距離;dave表示網(wǎng)絡(luò)中鄰居簇頭節(jié)點(diǎn)間距離的平均值，2節(jié)點(diǎn)距離越大，發(fā)送節(jié)點(diǎn)傳輸數(shù)據(jù)需要消耗的能量就越多，接收節(jié)點(diǎn)相對(duì)于發(fā)送節(jié)點(diǎn)來(lái)說(shuō)負(fù)擔(dān)就越重，負(fù)載度就越高；Ej表示節(jié)點(diǎn)sj當(dāng)前能量，Eave表示整個(gè)網(wǎng)絡(luò)中簇頭節(jié)點(diǎn)的平均能量；Ase和Are分別表示過(guò)去的t時(shí)間內(nèi)節(jié)點(diǎn)sj發(fā)送和接收的數(shù)據(jù)量；α、β、γ分別表示3個(gè)影響因素的權(quán)重大小且α+β+γ=1。

控制器根據(jù)網(wǎng)絡(luò)拓?fù)洌⒂邢蜻B通圖，采用Dijkstra算法，以節(jié)點(diǎn)負(fù)載度為鏈路權(quán)值，計(jì)算每個(gè)簇頭節(jié)點(diǎn)的最優(yōu)傳輸路徑。路徑公式如式(22)所示：

rcom(i,e)=argpmin∑si,sj∈p(i,e)Cj(i)

(22)

其中，rcom(i,e)表示針對(duì)普通數(shù)據(jù)的節(jié)點(diǎn)si至Sink節(jié)點(diǎn)的最佳路徑，節(jié)點(diǎn)so與節(jié)點(diǎn)sj為相鄰節(jié)點(diǎn)。

3.4 數(shù)據(jù)傳輸

控制器進(jìn)行路由計(jì)算后，下發(fā)流表至所有簇頭節(jié)點(diǎn)，流表中包含了針對(duì)不同類(lèi)型數(shù)據(jù)在傳輸時(shí)下一跳節(jié)點(diǎn)的地址等。當(dāng)感知節(jié)點(diǎn)有數(shù)據(jù)需要傳輸時(shí)，首先將數(shù)據(jù)包發(fā)送到自己的簇頭節(jié)點(diǎn)；然后簇頭節(jié)點(diǎn)對(duì)接收到的數(shù)據(jù)包進(jìn)行匹配，確定該數(shù)據(jù)包的類(lèi)型后，根據(jù)流表規(guī)則向下一跳簇頭節(jié)點(diǎn)發(fā)送該數(shù)據(jù)包，直至到達(dá)Sink節(jié)點(diǎn);最后Sink節(jié)點(diǎn)將數(shù)據(jù)打包后統(tǒng)一發(fā)送至控制器。

3.5 SDNUCQS算法流程

本文算法通過(guò)上述4個(gè)階段周期性進(jìn)行，但為了避免頻繁分簇，SDNUCQS在每一輪全局分簇后進(jìn)行輪局部簇頭更新。首先，在分簇階段完成后，控制器通過(guò)3.2節(jié)中的熵權(quán)法計(jì)算各個(gè)簇內(nèi)每個(gè)節(jié)點(diǎn)相對(duì)于該簇所有節(jié)點(diǎn)的綜合實(shí)力S，如果節(jié)點(diǎn)綜合實(shí)力大于δ倍的當(dāng)前簇頭節(jié)點(diǎn)綜合實(shí)力，則該節(jié)點(diǎn)可作為預(yù)備簇頭。一個(gè)簇內(nèi)預(yù)備簇頭的個(gè)數(shù)即該簇局部簇頭更新的次數(shù)。全網(wǎng)簇頭更新次數(shù)是所有簇的簇頭更新次數(shù)的平均值，如式(23)所示：

(23)

其中，kj為第j個(gè)簇的簇頭更新次數(shù)，num為全網(wǎng)中簇的總數(shù)。

SDNUCQS算法流程圖如圖5所示。

Figure 5 Flow chart of SDNUCQS algorithm 圖5 算法流程圖

4 仿真實(shí)驗(yàn)與結(jié)果分析

本文從全網(wǎng)簇頭能耗、端到端平均時(shí)延、平均傳輸丟失率和網(wǎng)絡(luò)生命周期4個(gè)方面進(jìn)行仿真，以驗(yàn)證SDNUCQS算法的性能，參數(shù)如表2所示。

Table 2 Simulation parameter

4.1 簇頭形成數(shù)量

Figure 6 Number of cluster heads formed圖6 簇頭形成數(shù)量

4.2 簇頭能耗對(duì)比

為了驗(yàn)證基于熵權(quán)法的簇頭選舉和非均勻分簇的有效性，選取若干輪，統(tǒng)計(jì)分簇結(jié)束后至下一輪分簇前，簇頭平均能耗，將SDNUCQS同LEACH、EEUC、CRIPSO和tPSOEB進(jìn)行比較，仿真結(jié)果如圖7所示。

Figure 7 Cluster head energy consumption圖7 簇頭能耗

EEUC、CRIPSO、tPSOEB和SDNUCQS同LEACH相比較，因其采用多跳路由且非均勻分簇，簇頭能耗明顯降低，且波動(dòng)較小。EEUC采用節(jié)點(diǎn)競(jìng)爭(zhēng)半徑公式實(shí)現(xiàn)非均勻分簇，避免能量空洞，平衡且降低簇頭能耗。CRIPSO通過(guò)粒子群優(yōu)化算法選舉出能量和位置更加合理的簇頭節(jié)點(diǎn)，簇頭能耗相比于EEUC進(jìn)一步降低了。而tPSOEB同樣采用基于粒子群優(yōu)化算法的簇頭選舉策略，但其采用SDN框架，簇頭無(wú)需路由計(jì)算等能量消耗，相比CRIPSO進(jìn)一步降低了能耗。本文的SDNUCQS基于SDN框架，采用熵權(quán)法進(jìn)行簇頭選舉并進(jìn)行非均勻分簇，簇頭能耗大小與tPSOEB較為接近且偏低。

4.3 時(shí)延對(duì)比

圖8為SDNUCQS的不同路由算法時(shí)延情況。rout1、rout2、rout3和rout4分別為時(shí)延敏感型數(shù)據(jù)、丟失率敏感型數(shù)據(jù)、時(shí)延和丟失率均敏感型數(shù)據(jù)和普通數(shù)據(jù)的路由。

Figure 8 End-to-end delay圖8 端到端時(shí)延

所有路由算法時(shí)延均隨運(yùn)行時(shí)間而增加。rout1和rout3傳輸?shù)臄?shù)據(jù)均對(duì)時(shí)延敏感，其路由計(jì)算中時(shí)延低于其他2個(gè)的；由于rout3以時(shí)延和丟失率共同作為參數(shù)，因此時(shí)延略高于rout1的。而rout2和rout4路由計(jì)算不考慮時(shí)延，則時(shí)延較高，但由于rout4為普通數(shù)據(jù)路由，以節(jié)點(diǎn)負(fù)載度為參數(shù)計(jì)算路徑，節(jié)點(diǎn)負(fù)載度低，間接性導(dǎo)致時(shí)延低，因此rout4時(shí)延略低于rout2的。rout1相較于rout2和rout4，傳輸時(shí)延平均降低29.62%和26.44%，rout3相較于rout2和rout4，傳輸時(shí)延平均降低25.57%和22.21%，由此可知SDNUCQS針對(duì)時(shí)延敏感型數(shù)據(jù)，能夠顯著降低端到端時(shí)延，提高網(wǎng)絡(luò)QoS。

4.4 丟失率對(duì)比

圖9為SDNUCQS不同路由數(shù)據(jù)丟失率情況，指標(biāo)設(shè)置同圖8。

Figure 9 Loss rate圖9 丟失率

rout2和rout3丟失率明顯低于rout1和rout4的，因?yàn)槠渎酚捎?jì)算均以丟失率為參數(shù)，得到傳輸丟失率最低的路徑，而rout3同時(shí)考慮時(shí)延參數(shù)，丟失率略高于rout2的。rout1僅考慮時(shí)延參數(shù)，所以傳輸丟失率高，rout4為普通數(shù)據(jù)路由，以節(jié)點(diǎn)負(fù)載度為參數(shù)，丟失率和rout1的接近。rout2與rout3傳輸丟失率區(qū)間分別為[0.24%,0.42%]和[0.43%,0.58%]，而rout1和rout4傳輸丟失率區(qū)間分別為[1.60%,1.75%]和[1.42%,1.68%]，可知SDNUCQS針對(duì)丟失率敏感型數(shù)據(jù)，能夠顯著降低傳輸丟失率。

4.5 網(wǎng)絡(luò)生命周期對(duì)比

圖10為SDNUCQS針對(duì)普通數(shù)據(jù)的路由以及LEACH、EEUC、CRIPSO和tPSOEB的網(wǎng)絡(luò)存活節(jié)點(diǎn)數(shù)量變化情況，從中可以比較網(wǎng)絡(luò)生命周期。

Figure 10 Network life cycle圖10 網(wǎng)絡(luò)生命周期

LEACH的存活節(jié)點(diǎn)數(shù)下降最快，在425輪左右節(jié)點(diǎn)全部死亡，EEUC采用非均勻分簇緩解網(wǎng)絡(luò)“熱區(qū)”問(wèn)題，有效延長(zhǎng)了網(wǎng)絡(luò)生命周期；CRIPSO利用粒子群優(yōu)化算法選擇更加合理的簇頭節(jié)點(diǎn)，平衡簇頭能耗，延長(zhǎng)生命周期；而tPSOEB和SDNUCQS利用SDN框架，節(jié)點(diǎn)無(wú)需路由計(jì)算，進(jìn)一步降低了簇頭能耗，SDNUCQS根據(jù)節(jié)點(diǎn)負(fù)載度計(jì)算路徑，均衡節(jié)點(diǎn)能耗，延長(zhǎng)網(wǎng)絡(luò)生命周期。SDNUCQS相比于LEACH、EEUC、CRIPSO和tPSOEB網(wǎng)絡(luò)生命周期分別延長(zhǎng)了50.58%,21.28%,13.70%和5.54%，由此可知SDNUCQS能夠平衡節(jié)點(diǎn)能耗，極大延長(zhǎng)網(wǎng)絡(luò)生命周期。

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

本文提出一種基于軟件定義的無(wú)線傳感器網(wǎng)絡(luò)非均勻分簇QoS路由算法SDNUCQS。簇頭選舉采用熵權(quán)法，結(jié)合QoS指標(biāo)，競(jìng)選出針對(duì)網(wǎng)絡(luò)QoS的高質(zhì)量簇頭。為緩解網(wǎng)絡(luò)熱區(qū)問(wèn)題，對(duì)網(wǎng)絡(luò)進(jìn)行非均勻分簇，平衡簇頭節(jié)點(diǎn)能耗。路由階段，首先按照時(shí)延和丟失率對(duì)數(shù)據(jù)分類(lèi)，然后控制器針對(duì)不同數(shù)據(jù)計(jì)算路由。仿真結(jié)果表明，SDNUCQS在分簇方面能有效提高簇頭質(zhì)量，降低簇頭能耗；在路由方面能夠顯著提高網(wǎng)絡(luò)QoS并且延長(zhǎng)網(wǎng)絡(luò)生命周期。雖然本文算法在仿真中具有較好的性能，但應(yīng)用于大規(guī)模網(wǎng)絡(luò)中的效果有待考量，下一步將進(jìn)一步改進(jìn)算法，使其在大規(guī)模網(wǎng)絡(luò)環(huán)境中也能發(fā)揮優(yōu)勢(shì)。