毛科技， 徐 慧， 方 凱， 陳慶章

(浙江工業(yè)大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，浙江 杭州 310023)

基于虛擬引力的WSNs路由協(xié)議設(shè)計(jì)與實(shí)現(xiàn)*

毛科技， 徐 慧， 方 凱， 陳慶章

(浙江工業(yè)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，浙江杭州310023)

數(shù)據(jù)采集是無線傳感器網(wǎng)絡(luò)(WSNs)主要功能之一，大規(guī)模的傳感器網(wǎng)絡(luò)采集并回收數(shù)據(jù)時(shí)容易出現(xiàn)節(jié)點(diǎn)負(fù)載不均衡，導(dǎo)致負(fù)載重的節(jié)點(diǎn)過早死亡。為了延長傳感器網(wǎng)絡(luò)的生存時(shí)間，本文提出了一種基于虛擬力的分簇路由協(xié)議(CRPVG)，選取合適的節(jié)點(diǎn)出任簇首；根據(jù)簇首與普通節(jié)點(diǎn)的虛擬引力大小進(jìn)行分簇；通過簇首之間多條傳輸將采集的數(shù)據(jù)包發(fā)送至基站節(jié)點(diǎn)。實(shí)驗(yàn)結(jié)果表明:提出的分簇路由協(xié)議在能耗均衡方面起到了較好的作用，延長了網(wǎng)絡(luò)的生存時(shí)間。

無線傳感器網(wǎng)絡(luò)； 分簇路由協(xié)議； 能量均衡； 虛擬引力

0 引 言

數(shù)據(jù)采集是無線傳感器網(wǎng)絡(luò)(wireless sensor networks,WSNs)主要作用之一，如監(jiān)測環(huán)境信息、監(jiān)測工廠附近污染物的擴(kuò)散等[1,2]。然而傳感器網(wǎng)絡(luò)需要采集轉(zhuǎn)發(fā)大量的數(shù)據(jù)，容易導(dǎo)致某些節(jié)點(diǎn)負(fù)載過重，能量消耗過快，最終導(dǎo)致傳感器網(wǎng)絡(luò)的過早死亡，因此,研究能耗均衡的路由協(xié)議有著重要的意義[3～6]。

在分簇路由協(xié)議方面的研究如比較有代表性的低功耗自適應(yīng)分簇路由協(xié)議[7](low energy adaptive clustering hierarchy，LEACH)，該協(xié)議首先利用隨機(jī)數(shù)隨機(jī)選取簇首，進(jìn)行分簇，簇首節(jié)點(diǎn)將簇成員節(jié)點(diǎn)采集的數(shù)據(jù)單跳發(fā)送至基站，LEACH路由協(xié)議隨機(jī)選取簇首，并不能避免傳感器網(wǎng)絡(luò)局部“過熱”問題，而且簇首單跳將數(shù)據(jù)發(fā)送至基站對傳感器節(jié)點(diǎn)硬件的要求較高，不適用于普通大型的傳感器網(wǎng)絡(luò)。針對LEACH路由協(xié)議隨機(jī)選取簇首存在的缺陷，文獻(xiàn)[8～11]均進(jìn)行了改進(jìn)，在簇首選取過程中綜合考慮了節(jié)點(diǎn)的剩余能量以及節(jié)點(diǎn)與其他節(jié)點(diǎn)的鏈路質(zhì)量等因素，較好地解決了LEACH路由協(xié)議存在的問題。文獻(xiàn)[12]提出了非均勻分簇的大小(unequal clustering size，UCS)路由協(xié)議，利用簇首的期望轉(zhuǎn)發(fā)負(fù)荷控制成簇規(guī)模，實(shí)驗(yàn)結(jié)果表明該路由協(xié)議能夠較好地均衡網(wǎng)絡(luò)負(fù)載，達(dá)到延長網(wǎng)絡(luò)生存時(shí)間的目的。文獻(xiàn)[13]提出了一種基于粒子群優(yōu)化(particle swarm optimization，PSO)算法的路由協(xié)議，該協(xié)議利用PSO算法優(yōu)化簇首。文獻(xiàn)[14，15]提出的路由協(xié)議均以網(wǎng)絡(luò)能耗為中心開展研究。文獻(xiàn)[16]提出了一種分布式能量均衡非均勻分簇(distributed energy-balanced unequal clustering，DEBUC)路由協(xié)議，該協(xié)議通過距離基站的距離，為簇首候選節(jié)點(diǎn)分配不同的競爭半徑,從而控制簇規(guī)模的大小。

目前，路由協(xié)議在分簇過程中很少考慮其合理性，在簇首多跳傳輸方面未全面考慮能耗均衡問題。本文提出了一種基于虛擬引力的分簇路由協(xié)議(clustering routing protocol based on virtual gravity,CRPVG)，在成簇階段，綜合考慮節(jié)點(diǎn)的剩余能量、節(jié)點(diǎn)與簇首節(jié)點(diǎn)間的信號(hào)強(qiáng)度，計(jì)算普通節(jié)點(diǎn)與其相鄰簇首節(jié)點(diǎn)間的引力，根據(jù)引力值選擇加入某個(gè)簇。分簇結(jié)束后，簇成員節(jié)點(diǎn)將數(shù)據(jù)包通過一跳的形式傳輸至簇首節(jié)點(diǎn)，最后簇首之間多跳將數(shù)據(jù)包傳輸至基站。

1 節(jié)點(diǎn)通信能耗模型

本文采用文獻(xiàn)[17]的節(jié)點(diǎn)通信能耗模型，發(fā)射數(shù)據(jù)包與接收數(shù)據(jù)包能耗模型如式(1)、式(2)所示。傳感器節(jié)點(diǎn)的能耗主要包括發(fā)射電路的能耗、信號(hào)放大電路的能耗和接收電路的能耗

Etx=k×Ee+k×εamp×d,

d≤dct=2,d>dc,t=4

(1)

Erx=k×Ee

(2)

式中Etx為發(fā)射總能耗；Erx為接收總能耗；Ee為發(fā)射和接收電路處理1 bit數(shù)據(jù)消耗的能量；k為發(fā)送或接收數(shù)據(jù)包的大小，bit；εamp為信號(hào)放大電路的放大倍數(shù)；d為節(jié)點(diǎn)間通信距離，dc為臨界距離，如式(3)所示

(3)

式中L為損耗因子，L≥1；hr和ht分別接收節(jié)點(diǎn)和發(fā)送節(jié)點(diǎn)天線與地面的高度；λ為載波波長，可根據(jù)傳感器節(jié)點(diǎn)的頻率計(jì)算。

2 分簇過程

2.1 簇首選舉

首先基站向傳感器網(wǎng)絡(luò)節(jié)點(diǎn)廣播信標(biāo)幀，利用洪泛法為每個(gè)節(jié)點(diǎn)建立鄰居節(jié)點(diǎn)列表，如文獻(xiàn)[17]中的方法。如傳感器節(jié)點(diǎn)i的鄰居節(jié)點(diǎn)列表中包括鄰居節(jié)點(diǎn)j的剩余能量Ej、節(jié)點(diǎn)i與節(jié)點(diǎn)j之間的信號(hào)強(qiáng)度RSSIij、節(jié)點(diǎn)i距離基站的最短跳數(shù)Hi以及鏈路質(zhì)量LQIij，每個(gè)傳感器節(jié)點(diǎn)i可獲得其自身的剩余能量Ei。

傳感器網(wǎng)絡(luò)中每個(gè)節(jié)點(diǎn)均根據(jù)其自身的鄰居節(jié)點(diǎn)列表信息計(jì)算其成為簇首的權(quán)重值wi，如果傳感器節(jié)點(diǎn)i的權(quán)重值wi是其通信范圍內(nèi)的最大值，則該節(jié)點(diǎn)出任簇首。wi值的計(jì)算綜合考慮了節(jié)點(diǎn)剩余能量、節(jié)點(diǎn)與鄰居節(jié)點(diǎn)的鏈路質(zhì)量以及信號(hào)強(qiáng)度值，如式(4)所示

(4)

式中α，β為常數(shù)，α+β=1;s為鄰居節(jié)點(diǎn)的數(shù)量；LQImax為鏈路質(zhì)量的最大值。wi值越大，表明節(jié)點(diǎn)i的剩余能量和與鄰居節(jié)點(diǎn)j的通信鏈路質(zhì)量均比較優(yōu)秀，成為簇首的可能性越大。

2.2 虛擬引力分簇

如圖1所示，C1，C2表示簇首傳感器節(jié)點(diǎn)，n1，n2表示普通傳感器節(jié)點(diǎn)，假設(shè)節(jié)點(diǎn)n1與簇首C1的虛擬引力為F1，與簇首C2的虛擬引力為F2，且F2>F1，則C1對n2的引力F3大于C2對n2的引力F4，因此，普通傳感器節(jié)點(diǎn)n2加入簇首C1對應(yīng)的簇。

圖1 虛擬引力

本文提出的虛擬引力與節(jié)點(diǎn)間的信號(hào)強(qiáng)度、節(jié)點(diǎn)的剩余能量相關(guān)，具體計(jì)算如式(5)所示

(5)

式中Em為簇首節(jié)點(diǎn)m的剩余能量；En為普通傳感器節(jié)點(diǎn)n的剩余能量；RSSImn為簇首節(jié)點(diǎn)m與普通傳感器節(jié)點(diǎn)n之間的信號(hào)強(qiáng)度(RSSImn<0)。當(dāng)Em越大，則其對普通節(jié)點(diǎn)n的虛擬引力越大，則能夠構(gòu)建規(guī)模較大的簇。當(dāng)簇首節(jié)點(diǎn)m與普通節(jié)點(diǎn)n之間的信號(hào)強(qiáng)度的平方越小時(shí)，表明節(jié)點(diǎn)m與n的距離越近，此時(shí)虛擬引力越大，越容易加入簇首m對應(yīng)的簇，節(jié)點(diǎn)n與簇首m的距離越近，通信能耗越小，因此，選擇距離其較近的簇首節(jié)點(diǎn)。

3 簇首多跳傳輸

完成網(wǎng)絡(luò)簇首的選擇和傳感器節(jié)點(diǎn)分簇后，簇成員傳感器節(jié)點(diǎn)將采集的數(shù)據(jù)通過一跳形式發(fā)送至簇首節(jié)點(diǎn)，簇首節(jié)點(diǎn)收到數(shù)據(jù)后進(jìn)行數(shù)據(jù)整合壓縮，然后將壓縮后的數(shù)據(jù)包通過簇首間多跳發(fā)送至基站。由于分簇后簇首與簇首之間的距離增加，因此，傳感器節(jié)點(diǎn)被選舉為簇首后立即將自身的通信半徑r調(diào)整為γ·r，γ>1。

簇首一方面需要采集并轉(zhuǎn)發(fā)其簇首成員的數(shù)據(jù)包、同時(shí)還需要接收并轉(zhuǎn)發(fā)其他簇首發(fā)送的數(shù)據(jù)包，因此，簇首的能耗非常重要，倘若某條路由路徑上的簇首轉(zhuǎn)發(fā)負(fù)載過重，則該路徑中的簇首節(jié)點(diǎn)容易提早死亡，對傳感器網(wǎng)絡(luò)的傷害非常大，因此，簇首多跳傳輸過程中主要考慮簇首之間能耗均衡性問題。

為了均衡簇首之間數(shù)據(jù)包轉(zhuǎn)發(fā)的能耗，設(shè)計(jì)簇首之間轉(zhuǎn)發(fā)消息的代價(jià)函數(shù)，如式(6)所示

(6)

式中a，b為常數(shù)，且a+b=1；E0為傳感器節(jié)點(diǎn)的初始能量；Ecj為簇首節(jié)點(diǎn)cj的剩余能量；Hcj為簇首節(jié)點(diǎn)cj距離基站的最短跳數(shù)；Hmax為網(wǎng)絡(luò)中傳感器節(jié)點(diǎn)距離基站的最大最短跳數(shù)。當(dāng)節(jié)點(diǎn)ci需要發(fā)送數(shù)據(jù)時(shí)，其根據(jù)其鄰居節(jié)點(diǎn)列表中的相關(guān)信息計(jì)算鄰居簇首節(jié)點(diǎn)cj作為簇首ci下一跳轉(zhuǎn)發(fā)節(jié)點(diǎn)的代價(jià)。簇首ci會(huì)選擇代價(jià)最小的鄰居簇首節(jié)點(diǎn)cj作為其下一跳轉(zhuǎn)發(fā)節(jié)點(diǎn)。

根據(jù)代價(jià)函數(shù)可知，當(dāng)某個(gè)簇首節(jié)點(diǎn)cj經(jīng)常為簇首節(jié)點(diǎn)ci轉(zhuǎn)發(fā)數(shù)據(jù)包時(shí)，其剩余能量Ecj會(huì)降低，從而轉(zhuǎn)發(fā)代價(jià)會(huì)增加，簇首節(jié)點(diǎn)ci會(huì)自動(dòng)選擇其他簇首節(jié)點(diǎn)作為其下一跳轉(zhuǎn)發(fā)節(jié)點(diǎn)。因此，本文設(shè)計(jì)的代價(jià)函數(shù)能夠較好地發(fā)揮簇首間能耗均衡的作用。

4 實(shí) 驗(yàn)

傳感器網(wǎng)絡(luò)部署區(qū)域?yàn)?00 m×500 m，在區(qū)域中隨機(jī)部署700個(gè)傳感器節(jié)點(diǎn)，初始時(shí)刻傳感器節(jié)點(diǎn)的通信半徑r=25 m，節(jié)點(diǎn)被選舉為簇首后，簇首的通信半徑自動(dòng)調(diào)整為2r。傳感器網(wǎng)絡(luò)定時(shí)采集數(shù)據(jù)，采集450次數(shù)據(jù)后重新選擇簇首并且重新分簇，完成一輪簇首選舉。網(wǎng)絡(luò)各項(xiàng)參數(shù)設(shè)置如下：Ee為50 nJ/bit;如果d

4.1 網(wǎng)絡(luò)剩余能量的均值與方差

傳感器節(jié)點(diǎn)的剩余能量均值如圖2所示。

圖2 傳感器網(wǎng)絡(luò)剩余能量均值

實(shí)驗(yàn)結(jié)果表明:本文提出的路由協(xié)議CRPVG的剩余能量均值高于LEACH路由協(xié)議，由于LEACH路由協(xié)議要求簇首將數(shù)據(jù)包直接發(fā)送至基站，而簇首距離基站較遠(yuǎn)，要求額外的遠(yuǎn)程通信硬件設(shè)備工作，該過程會(huì)消耗大量的能量；而CRPVG路由協(xié)議中簇首將簇成員的數(shù)據(jù)包進(jìn)行整合并通過多跳傳輸至基站，不必消耗額外的能耗；基于Dijkstra的最短路徑路由協(xié)議未選舉簇首，傳感器節(jié)點(diǎn)采集數(shù)據(jù)后通過節(jié)點(diǎn)間多跳將數(shù)據(jù)傳輸至基站，該過程中需要大量的傳感器節(jié)點(diǎn)參與傳輸，消耗了較多的能量，因此，傳感器網(wǎng)絡(luò)剩余能量均值最低。

傳感器節(jié)點(diǎn)的剩余能量方差如圖3所示。

圖3 傳感器網(wǎng)絡(luò)剩余能量方差

當(dāng)簇首選舉輪數(shù)小于2時(shí)， CRPVG路由協(xié)議和LEACH路由協(xié)議的網(wǎng)絡(luò)剩余能量方差均大于基于Dijkstra的最短路徑路由協(xié)議。在初始時(shí)刻，本文提出的CRPVG和LEACH路由協(xié)議成簇過程中消耗能量不均衡，導(dǎo)致了方差大于基于Dijkstra的最短路徑路由協(xié)議。隨著傳感器網(wǎng)絡(luò)的運(yùn)行，CRPVG能夠較好地均衡網(wǎng)絡(luò)的能耗，因此方差最??；其次為LEACH分簇路由協(xié)議的方差，而基于Dijkstra的最短路徑路由協(xié)議方差最大。因?yàn)殡S著網(wǎng)絡(luò)的運(yùn)行，最短路徑路由協(xié)議不會(huì)根據(jù)鏈路中節(jié)點(diǎn)能量的消耗而動(dòng)態(tài)調(diào)整鏈路路徑，所以某些鏈路能量消耗大，網(wǎng)絡(luò)的剩余能量方差最大。

4.2 傳感器網(wǎng)絡(luò)死亡節(jié)點(diǎn)數(shù)量

傳感器網(wǎng)絡(luò)中死亡節(jié)點(diǎn)的數(shù)量與簇首選舉輪數(shù)的關(guān)系如圖4所示。

圖4 死亡節(jié)點(diǎn)實(shí)驗(yàn)

實(shí)驗(yàn)結(jié)果表明：CRPVG路由協(xié)議最晚出現(xiàn)死亡節(jié)點(diǎn)，而基于Dijkstra的最短路徑路由協(xié)議最早出現(xiàn)死亡節(jié)點(diǎn)，且傳感器網(wǎng)絡(luò)運(yùn)行在同一時(shí)刻，最短路徑路由協(xié)議出現(xiàn)死亡節(jié)點(diǎn)的數(shù)量最多，而CRPVG路由協(xié)議出現(xiàn)死亡節(jié)點(diǎn)的數(shù)量最少，因?yàn)楸疚奶岢龅腃RPVG路由協(xié)議具有較好的能耗均衡性，而最短路徑路由協(xié)議并不能動(dòng)態(tài)地選擇路由路徑，因此，出現(xiàn)了上述實(shí)驗(yàn)結(jié)果。

5 結(jié) 論

提出了一種基于虛擬引力的分簇路由協(xié)議，綜合考慮節(jié)點(diǎn)剩余能量、節(jié)點(diǎn)與相鄰節(jié)點(diǎn)的鏈路質(zhì)量選舉簇首，然后利用虛擬引力進(jìn)行普通節(jié)點(diǎn)入簇，最后簇首間以多跳的形式將數(shù)據(jù)包發(fā)送至基站。實(shí)驗(yàn)結(jié)果驗(yàn)證了提出的路由協(xié)議能夠較好的均衡網(wǎng)絡(luò)的能耗，而且該路由協(xié)議沒有過高的軟硬件條件，適用于普通的傳感器網(wǎng)絡(luò)。

[1] 董夢夢,王 翥.面向機(jī)場環(huán)境監(jiān)測的 WSNs組網(wǎng)技術(shù)[J].江蘇大學(xué)學(xué)報(bào): 自然科學(xué)版,2016,37(5): 578-584.

[2] 魏 東,全 元,王辰星,等.國家大型煤電基地生態(tài)環(huán)境監(jiān)測技術(shù)體系研究——以內(nèi)蒙古錫林郭勒盟煤電基地為例[J].生態(tài)學(xué)報(bào),2014,34(11): 2821-2829.

[3] 曹 健,王興偉,張金宏,等.數(shù)據(jù)驅(qū)動(dòng)的信息中心網(wǎng)絡(luò)認(rèn)知路由協(xié)議[J].計(jì)算機(jī)研究與發(fā)展,2015,52(4):798-805.

[4] Zheng B,Cui B T.A routing protocol for WSNs based on chaotic PSO and ant colony algorithm[J].Electronic Design Engineering,2015,45(5):706-715.

[5] Brar G S,Rani S,Chopra V,et al.Energy efficient direction-based PDORP routing protocol for WSNs[J].IEEE Access,2016,4:3182-3194.

[6] Zhu J,Liu J,Hai Z,et al.Research on routing protocol facing to signal conflicting in link quality guaranteed WSNs[J].Wireless Networks,2016,22(5):1739-1750.

[7] Heinzelman W R,Chandrakasan A,Balakrishnan H.Energy-efficient communication protocol for wireless microsensor networks[C]∥2000 Proceedings of the 33rd Annual Hawaii International Conference on System Sciences,IEEE,2000: 10.

[8] 白永祥.一種LEACH路由協(xié)議算法的改進(jìn)與分析[J].通信技術(shù),2015,48(9):1062-1067.

[9] Heinzelman W B,Chandrakasan A P,Balakrishnan H.An application specific protocol architecture for wireless microsensor networks[C]∥IEEE Transactions on Wireless Communication,2002:660-670.

[10] Mehmood A,Lloret J,Noman M,et al.Improvement of the wireless sensor networks lifetime using LEACH with vice-cluster head[J].Ad Hoc & Sensor Wireless Networks,2015,28(1):1-17.

[11] Arumugam G S,Ponnuchamy T.EE-LEACH: Development of energy-efficient LEACH protocol for data gathering in WSNs[J].EURASIP Journal on Wireless Communications and Networking,2015,2015(1):1-9.

[12] Soro S,Heinzelman W B.Prolonging the lifetime of wireless sensor networks via unequal clustering[C]∥Proceedings of the 19th IEEE International Parallel and Distributed Processing Symposium,IEEE,2005:8.

[13] Latiff N M A,Tsimenidis C C,Sharif B S.Energy-aware clustering for wireless sensor networks using particle swarm optimiza-tion[C]∥IEEE International Symposium on Personal,Indoor and Mobile Radio Communications,IEEE,2007:1-5.

[14] 王改云,胡錦艷.基于簇的路由協(xié)議比較[J].傳感器與微系統(tǒng),2016,35(4):4-7.

[15] 何燕清,鄧華秋.基于能量梯度改進(jìn)的GPSR協(xié)議[J].傳感器與微系統(tǒng),2016,35(12):44-47.

[16] 蔣暢江,石為人,唐賢倫,等.能量均衡的無線傳感器網(wǎng)絡(luò)非均勻分簇路由協(xié)議[J].軟件學(xué)報(bào),2012,34(5):1222-1232.

[17] 周 雪,朱小明,陳立建,等.基于停車誘導(dǎo)系統(tǒng)的能量均衡可靠路由協(xié)議的設(shè)計(jì)[J].傳感技術(shù)學(xué)報(bào),2015,28(9):1408-1417.

DesignandrealizationofWSNsroutingprotocolbasedonvirtualgravity*

MAO Ke-ji, XU Hui, FANG Kai, CHEN Qing-zhang

(CollegeofComputerScienceandTechnology,ZhejiangUniversityofTechnology,Hangzhou310023,China)

One of the main uses of wireless sensor networks(WSNs) is data acquisition.Large-scale sensor networks are prone to load imbalance in nodes when collecting and reclaiming data,which leads to premature death of heavy load nodes.In order to prolong the survival time of the sensor network,propose a clustering routing protocol based on virtual gravity(CRPVG).The protocol chooses appropriate nodes as cluster head,and according to size of the virtual gravity of cluster head and normal nodes for clustering,send collected data packets to the base station nodes through multiple transmission between cluster head nodes.The experimental results show that the proposed clustering routing protocol can play good role in energy balance and prolong the survival time of the network.

wireless sensor networks(WSNs); clustering routing protocol; energy balance; virtual gravity

10.13873/J.1000—9787(2017)12—0098—04

TP 212

A

1000—9787(2017)12—0098—04

2017—10—13

國家自然科學(xué)基金資助項(xiàng)目(61379023)；浙江省公益性技術(shù)應(yīng)用研究計(jì)劃項(xiàng)目(LGG18F020018)

毛科技(1979-)，男，博士，副教授，碩士生導(dǎo)師，主要從事物聯(lián)網(wǎng)技術(shù)，大數(shù)據(jù)分析相關(guān)方面的研究工作，E-mail:maokeji@zjut.edu.cn。陳慶章(1955-)，男，博士，教授，博士生導(dǎo)師，主要從事無線傳感器網(wǎng)絡(luò)相關(guān)研究工作，E-mail:qzchen@zjut.edu.cn。