一種面向智能電網(wǎng)的無線傳感器網(wǎng)絡(luò)簇路由算法

張鼎興

(廣東水利電力職業(yè)技術(shù)學院 計算機信息工程系，廣東 廣州 510635)

?

一種面向智能電網(wǎng)的無線傳感器網(wǎng)絡(luò)簇路由算法

張鼎興

(廣東水利電力職業(yè)技術(shù)學院 計算機信息工程系，廣東 廣州 510635)

面向智能電網(wǎng)的無線傳感器網(wǎng)絡(luò)(wireless sensor network，WSN)是由多個以電塔為中心的區(qū)域組成，使得這種WSN呈窄長的拓撲結(jié)構(gòu)，根據(jù)這種拓撲結(jié)構(gòu)設(shè)計了一種基于分簇的路由算法FCHR (Fore-elected Cluster Head Routing Algorithm)。FCHR首先采用分布式的方法生成候選簇頭，然后在候選簇頭中產(chǎn)生每個區(qū)域的簇頭，進而生成由所有簇頭組成的路由。仿真顯示FCHR算法產(chǎn)生的簇頭是LEACH算法的25.4%，而網(wǎng)絡(luò)的生命周期提高了近40%。

遠程監(jiān)控；候選簇頭；簇頭；數(shù)據(jù)報文；生命周期

0 引言

智能電網(wǎng)技術(shù)通過傳感器和通信網(wǎng)絡(luò)遠程監(jiān)控電網(wǎng)的運行狀態(tài)，這個監(jiān)控網(wǎng)絡(luò)能否可靠傳輸現(xiàn)場狀態(tài)數(shù)據(jù)到控制中心是關(guān)鍵。由于電網(wǎng)所處的地理環(huán)境非單一性并且范圍較廣，使得整個電網(wǎng)環(huán)境數(shù)據(jù)采集點分布不集中，而且很多監(jiān)測點所處的環(huán)境比較惡劣，布置光纖之類的監(jiān)控網(wǎng)絡(luò)設(shè)施難度大、成本高。WSN成本低、組網(wǎng)靈活，并且能適應(yīng)復雜環(huán)境下數(shù)據(jù)采集，可以彌補光纖網(wǎng)絡(luò)在一些地區(qū)布網(wǎng)難度大的問題。而且，由于有些監(jiān)控區(qū)域受基站所處位置的影響會產(chǎn)生覆蓋盲區(qū)，WSN也可以彌補無線寬帶接入方案的信號盲區(qū)問題。

WSN可提供靈活而經(jīng)濟的監(jiān)控網(wǎng)絡(luò)的解決方案。但是，如何保證傳輸實時性好而且可靠的數(shù)據(jù)，設(shè)計性能良好的WSN路由協(xié)議是提供可靠通信保證的關(guān)鍵問題之一。

很多研究者已經(jīng)提出了各種WSN路由協(xié)議。根據(jù)電網(wǎng)的分布特點，采用分簇路由算法比較適合智能電網(wǎng)的WSN路由構(gòu)造，分簇路由算法是在簇頭的基礎(chǔ)上實現(xiàn)的，產(chǎn)生簇頭是簇路由算法的關(guān)鍵。近年來，有許多關(guān)于WSN的簇路由算法的研究。

LEACH算法[1]采用等概率方式隨機選擇簇頭，每個節(jié)點根據(jù)隨機數(shù)自主決定是否當選簇頭，每輪產(chǎn)生的簇頭沒有確定的數(shù)量和位置，平均分配整個網(wǎng)絡(luò)的能量負載，達到降低網(wǎng)絡(luò)能耗，從而延長網(wǎng)絡(luò)生命周期。Heinzelman W提出了一種集中式產(chǎn)生簇頭的LEACH-C算法[2]和LEACH-F算法[2]，這種算法由中心節(jié)點選擇簇頭，每個節(jié)點必須告知所在的地理位置以及剩余能量給中心節(jié)點，中心節(jié)點通過計算平均剩余能量，選擇剩余能量不低于平均剩余能量的節(jié)點作為候選簇頭，再采用模擬退火算法從候選節(jié)點中選出合適數(shù)量的簇頭集合。LEACH．F則是LEACH的改變，按照LEACH-C的簇形成方式，但每個簇都有一個當選簇頭的節(jié)點輪流表。

GREES-L算法[3]和 GREES-M算法[3]是兩種利用地理路由和能量路由技術(shù)相結(jié)合的路由協(xié)議，這種路由協(xié)議節(jié)點能從環(huán)境中獲得能量為前提，雖然算法的路由決策速度快比較快，但這種協(xié)議沒有考慮網(wǎng)絡(luò)擁塞的問題。Chipara, Z. 等人提出一種能量感知 QoS 路由協(xié)議[4]，這種路由協(xié)議通過發(fā)現(xiàn)能耗和延遲低的鏈路保證實時數(shù)據(jù)的傳輸。RPAR[5]算法是一種實時能量感知的路由協(xié)議，這協(xié)議通過動態(tài)調(diào)節(jié)發(fā)送能量和路由判決解決低能耗的實時通信，通過能量感知的上游策略和有效的鄰居節(jié)點管理器優(yōu)化資源受限的WSN。對于有損鏈路、可伸縮性、內(nèi)存及其有限以及帶寬受限的WSN也提供了一種路由選擇機制的解決方案。AODV算法[6]通過估算傳感器節(jié)點向sink傳輸數(shù)據(jù)包所需消耗的能量，提出一種基于分層結(jié)構(gòu)的分簇低能耗路由協(xié)議，利用隨機循環(huán)選擇簇頭節(jié)點，將整個網(wǎng)絡(luò)的能量負載平均分配到每個傳感器節(jié)點中，達到降低網(wǎng)絡(luò)能耗來提高網(wǎng)絡(luò)整體生存時間的目的。與一般的基于平面結(jié)構(gòu)的路由協(xié)議和靜態(tài)的基于多簇結(jié)構(gòu)的路由協(xié)議相比，這些路由協(xié)議在高能效的基礎(chǔ)上可以有效減少端到端的數(shù)據(jù)傳輸延遲。

通過在網(wǎng)絡(luò)運行前由終端用戶將布置的網(wǎng)絡(luò)節(jié)點劃分成多個簇的方式，Mohamed Younis等人提出了WSN三層結(jié)構(gòu)的路由協(xié)議[7]，這種協(xié)議必須將簇頭標識和成員節(jié)點的位置告知每個簇頭，再由簇頭根據(jù)本簇內(nèi)節(jié)點發(fā)布的狀態(tài)數(shù)據(jù)監(jiān)測各節(jié)點的能量變化。路由選擇以代價函數(shù)和節(jié)點間數(shù)據(jù)傳輸鏈路成本來確定，代價函數(shù)包含了節(jié)點間距離、能量消耗、傳輸延遲等因素這些參數(shù)，這種協(xié)議具有能效較高、通信延遲較低以及能進行擁塞控制的特點。

1 基于FCHR算法的WSN的特點

智能電網(wǎng)遠程監(jiān)控系統(tǒng)的WSN由人工部署，感知范圍、通信半徑以及節(jié)點布置的位置可預(yù)先規(guī)劃，在網(wǎng)絡(luò)生命周期內(nèi)可以保證WSN的連通性和可靠性。如圖1所示，WSN部署在電塔或者輸電線上沿著電網(wǎng)呈窄長鏈狀拓撲結(jié)構(gòu)。

圖1 智能電網(wǎng)傳感器節(jié)點分布示意圖Fig.1 Sensor node distribution in Smart Grid

根據(jù)智能電網(wǎng)的WSN網(wǎng)絡(luò)的特點，考慮n個傳感器節(jié)點S={s1s2…sn}分布在電塔及其鄰近區(qū)域A內(nèi)，WSN模型的基本假設(shè)如下：

● 傳感器節(jié)點發(fā)送功率可調(diào)，通過調(diào)節(jié)發(fā)射功率，每個傳感器節(jié)點都能與其相鄰的電塔上的傳感器節(jié)點通信；

● 每個節(jié)點知道自身的位置及其上、下行方向；

● 每個節(jié)點在布置時已知區(qū)域A內(nèi)每個節(jié)點ID。

由以上假設(shè)可知相鄰電塔間的傳感器節(jié)點是全連通圖，其拓撲如圖2 所示。

圖2 相鄰電塔傳感器網(wǎng)絡(luò)拓撲示意圖Fig.2 Sensor network topology in adjacent high voltage towers

2 FCHR算法描述

根據(jù)智能電網(wǎng)的WSN的拓撲結(jié)構(gòu)特點，為了提高網(wǎng)絡(luò)的生命周期和可靠性，必須設(shè)計一種合適的分簇路由協(xié)議來滿足面向智能電網(wǎng)的WSN的應(yīng)用要求。智能電網(wǎng)的WSN簇可按照以電塔為中心的所有鄰接節(jié)點劃分，如圖1中的A和B，可以在布置時讓每個節(jié)點保存本簇節(jié)點成員表。通過路由算法將網(wǎng)絡(luò)中的節(jié)點劃分為如圖3所示的簇頭和普通節(jié)點，簇頭負責收集本簇內(nèi)普通節(jié)點轉(zhuǎn)發(fā)的數(shù)據(jù)。這些數(shù)據(jù)經(jīng)過數(shù)據(jù)融合后再發(fā)往其上游的簇頭，最后到達sink；同時，簇頭還負責轉(zhuǎn)發(fā)來自監(jiān)控中心的指令以及來自其下游簇頭的數(shù)據(jù)包。由此可知，簇頭節(jié)點是數(shù)據(jù)包的轉(zhuǎn)發(fā)和數(shù)據(jù)融合中心，能量消耗較大，特別是越臨近sink的簇頭，通信負荷越重，能量消耗也越大。為了平衡網(wǎng)絡(luò)在其生命周期內(nèi)的負載均衡，延長網(wǎng)絡(luò)的生命周期，設(shè)計面向智能電網(wǎng)的WSN的路由算法時應(yīng)盡可能避免反復選舉同一個節(jié)點作為簇頭。根據(jù)上述要求設(shè)計的FCHR算法由決定候選簇頭選舉、簇頭選舉和路由生成三個步驟組成。

圖3 智能電網(wǎng)傳感器網(wǎng)絡(luò)抽象圖Fig.3 Sensor network abstract graph in Smart Grid

2.1 候選簇頭選舉

首先，各節(jié)點采用分布式算法決定是否候選簇頭，所謂候選簇頭，當且僅當Thresh≥K，其中K為一個給定范圍內(nèi)的隨機數(shù)，閾值Thresh按照下列方式設(shè)置：

(1)

在(1)式中：ω表示節(jié)點u已被選為簇頭的次數(shù)，Eu表示節(jié)點u的剩余能量，Eu0表示節(jié)點u的初始能量，du表示節(jié)點u到上游電塔中心點的距離，考慮到發(fā)射功率與傳輸距離是2～5次方，k表示與發(fā)射頻率相關(guān)的比例常數(shù)。

當節(jié)點u為候選簇頭時，就向預(yù)設(shè)的簇內(nèi)所有成員發(fā)送CANDIDATE報文，將自己的初始能量、剩余能量、到上游電塔中心點的距離以及已被選為簇頭的次數(shù)告知其它的候選簇頭，非候選簇頭則丟棄CANDIDATE報文。其中CANDIDATE報文格式如下：

MessageHeadEuEu0duω

2.2 簇頭選舉

當候選簇頭的選舉完成后，每個候選簇頭都保存了一份本簇其它候選簇頭信息表，然后根據(jù)這些信息選舉簇頭。候選簇頭能否當選為簇頭由是否能發(fā)送CLUSTERHEAD報文來決定。簇頭選舉階段分候選簇頭和普通節(jié)點兩種情況處理。

1)對于普通節(jié)點，當接收到的第一個CLUSTERHEAD報文時，即將發(fā)送該報文的節(jié)點作為其簇頭。

(2)

然后通過求這m個候選簇頭評價值最大者ElectValue=Max(σ1,σ2…,σm)決定是否當選簇頭。

如果σi=ElectValue，在等待一個隨機后退時間ti后，節(jié)點ui向所在的電塔區(qū)域內(nèi)的所有節(jié)點發(fā)送CLUSTERHEAD報文。如果ui在ti內(nèi)接收到其它節(jié)點的CLUSTERHEAD報文，那么ui停止發(fā)送CLUSTERHEAD報文，并將接收到的第一個CLUSTERHEAD報文的節(jié)點作為簇頭。

從式(2)可以看出，每個候選簇頭評價值是由到上游電塔中心點的距離、當選簇頭的次數(shù)以及剩余能量三個參數(shù)做為綜合評價指標，這種方式是為了盡可能實現(xiàn)網(wǎng)內(nèi)節(jié)點能耗均衡。CLUSTERHEAD報文格式如下：

MessageHeaduID

為了提高網(wǎng)絡(luò)的實時性，每個電塔所在區(qū)域內(nèi)的所有節(jié)點在完成數(shù)據(jù)傳輸后，必須重新進行下一輪的簇頭的選舉。

2.3 路由生成

經(jīng)過候選簇頭選舉、簇頭選舉兩個階段，當選為簇頭的節(jié)點再向其下游電塔所在區(qū)域內(nèi)的簇頭發(fā)送PRECEDING報文，告知自己的ID；每個下游簇頭將接收到的第一個PRECEDING報文的簇頭作為下一跳節(jié)點而建立路由表。PRECEDING報文格式如下：

MessageHeaduID

3 性能評估

本節(jié)通過仿真對FCHR算法的性能進行評估?？紤]部署在二維平面上的靜態(tài)WSN，100個傳感器節(jié)點隨機分布在兩個50m×50m且相距200m的矩形區(qū)域，分別記作區(qū)域I和區(qū)域II，每個區(qū)域布置50個節(jié)點，這些節(jié)點的ID從1～100進行標識，區(qū)域I的節(jié)點ID從1～50，區(qū)域II標識從51～100。每個節(jié)點無線通信半徑可從0～300m調(diào)節(jié)。仿真實驗在NS2模擬平臺進行。

3.1 算法生成簇頭的個數(shù)

仿真實驗將FCHR算法與LEACH算法生成簇頭的個數(shù)進行比較，實驗進行20次，圖4給出了FCHR算法與LEACH算法生成簇頭個數(shù)在執(zhí)行20次的比較。

從仿真結(jié)果可以看出，F(xiàn)CHR算法每次產(chǎn)生的簇頭個數(shù)平均為1.4個，而LEACH算法生成簇頭個數(shù)平均為5.5個，因而FCHR算法與LEACH算法更有利于簇頭的生成。對于只需要一個簇頭與其上游簇頭或者下游簇頭即可通信的WSN，由單個簇頭完成本簇成員數(shù)據(jù)融合并路由到上游簇頭，可大大減少多個簇頭節(jié)點轉(zhuǎn)發(fā)數(shù)據(jù)造成的能耗，可有效提高網(wǎng)絡(luò)的生命周期。

圖4 FCHR與LEACH算法生成簇頭個數(shù)比較Fig.4 Comparison of cluster head number between FCHR and LEACH

3.2 網(wǎng)絡(luò)的生命周期

對于一個簇的簇頭節(jié)點，需要承擔以下任務(wù)：1)采集現(xiàn)場物理數(shù)據(jù)，2)產(chǎn)生路由，3)接收并轉(zhuǎn)發(fā)來自上一跳簇頭的數(shù)據(jù)，4)接收并融合和發(fā)送本簇節(jié)點的數(shù)據(jù)。在仿真實驗中，假設(shè)簇頭在以上5方面消耗能量，并且當簇中有10%的節(jié)點死亡時，認為該網(wǎng)絡(luò)的生命周期結(jié)束。假設(shè)每個節(jié)點的初始能量為1個能量單位，每個報文的長度為100字節(jié)，每接收1字節(jié)消耗的能量為1×10-5個能量單位，即每接收一個報文需要消耗1×10-3個能量單位。傳感器節(jié)點發(fā)送數(shù)據(jù)所消耗的能量不僅與發(fā)送的字節(jié)數(shù)有關(guān)，而且與發(fā)送距離有關(guān)，假設(shè)每個節(jié)點發(fā)送數(shù)據(jù)每米每字節(jié)消耗1×10-6個能量單位，簇頭節(jié)點每次用于數(shù)據(jù)融合消耗1×10-3的能量單位，每個傳感器節(jié)點用于采集和處理數(shù)據(jù)每次消耗1×10-3的能量單位。

圖5 兩種算法的工作次數(shù)與存活節(jié)點關(guān)系Fig.5 Relation of running frequency and active nodes between FCHR and LEACH

從圖5可以看出，F(xiàn)CHR算法在第43次時活躍節(jié)點數(shù)才降至10%以下，而LEACH算法在第22次時活躍節(jié)點數(shù)就降至10%以下。由于兩種算法每次產(chǎn)生簇頭數(shù)相差很大，造成電塔之間的簇頭與簇頭交換數(shù)據(jù)的次數(shù)更多，從而引起簇頭能量消耗更快，說明FCHR算法可大大提高網(wǎng)絡(luò)的生命周期。

4 結(jié)束語

由于整個智能電網(wǎng)的WSN的節(jié)點不是集中布置在一個區(qū)域，而是由許多相隔較遠的呈現(xiàn)成窄長的多個區(qū)域組成，根據(jù)應(yīng)用的需要每個區(qū)域內(nèi)節(jié)點比較密集。根據(jù)這種拓撲結(jié)構(gòu)設(shè)計的基于分簇的路由算法FCHR，可以減少不同區(qū)域間的節(jié)點通信次數(shù)，從而提高全網(wǎng)的生命周期。通過仿真可以看出，利用FCHR算法產(chǎn)生的簇頭是LEACH算法的25.4%，而網(wǎng)絡(luò)的生命周期提高了將近40%。

[1] HEINZELMAN W，CHANDRAKASAN A，BALAKRISHNA H．Energy-Efficient communication protocol for wire

less microsensor networks[C]．in Proceedings of the Hawaii International Conference on Systems Sciences, Hawai,2000:3005-3014．

[2] W HEINZELMAN．Application-Specific protocol architectures for wireless networks [D/OL]．Boston：Massachusetts Institute of Technology，2000：98-109[2016-03-04].http://www.ece.rochester.edu/～wheinzel/research.html．

[3] ZENG K,REN K,LOU W,et al.Energy Aware Efficient Geographic Routing in Lossy Wireless Sensor Networks with Environmental Energy Supply[J].Wireless Networks,2009,15(1): 39-51.

[4] AKKAYA K,YOUNIS M.Energy and QoS aware routing in wireless sensor networks[J].Cluster Computing The Journal of Networks Software Tools and Applications,2005,8:179-188.

[5] CHIPARA O,HE Z,XING G,et al.Real-Time Power-Aware Routing in Sensor Networks[J].Iwqos,2006:83-92.

[6] KALYANI K,MAMTA S.An Energy Efficient and QoS Aware Routing Protocol for Wireless Sensor Network [J].International Journal of Advanced Research in Computer and Communication Engineering,2015,4(7)：355-358.

[7] MOHAMED Y，MOUSTAFA Y，KHALED A.Energy-Aware Routing in Cluster-Based Sensor Networks[C].The 10thIEEE International Symposium on Modeling,Analysis and Simulation of Computer and Telecommunications Systems,Fort Worth,Texas,2002,129-136.

A cluster-based routing algorithm for wireless sensor networks facing smart grid

ZHANG Dingxing

(Department of Computing and Information Technology，Guangdong Technical College of Water Resources and Electric Engineering，Guangzhou,Guangdong 510635，China)

Wireless sensor networks(WSN) facing smart grid is composed of many areas centered as power tower, which makes WSN become long and narrow topology. Based on this topology, Fore-elected cluster head routing algorithm is designed. Firstly, using distributed approach; FCHR generates fore-elected cluster, and then generates cluster head for each area among fore-elected cluster. Finally, a route composed of all cluster heads is generated. The simulation shows cluster head generated by FCHR algorithm is 25.4% of LEACH algorithm. However, the network lifetime is increased by nearly 40%.

remote monitor and control;fore-elected cluster;cluster head;data message;lifetime

1004—5570(2016)05-0093-05

2016-07-05

張鼎興(1965-),男，博士，副教授,研究方向：分布式計算、網(wǎng)絡(luò)安全，E-mail：sliversea@163.com.

TP393

A