李良 吳念 王崢 孫海全 武穆清

（1.北京智芯微電子科技有限公司 北京市 100192 2.北京郵電大學(xué) 北京市 100876）

隨著國(guó)家對(duì)智能電網(wǎng)項(xiàng)目的重視以及電力系統(tǒng)狀態(tài)檢修等工作的展開，輸電線路在線監(jiān)測(cè)的相關(guān)技術(shù)也得到了迅猛發(fā)展。而傳感器網(wǎng)絡(luò)因能通過對(duì)輸電線路各種運(yùn)行參數(shù)進(jìn)行在線監(jiān)測(cè)，且集信息采集、傳輸和處理一體，綜合傳感器、嵌入式計(jì)算、無線通信以及分布式信息處理等技術(shù)，已成為智能電網(wǎng)領(lǐng)域一種非常重要的技術(shù)手段，被稱作是“智能信息感知末梢”。輸電線路智能間隔棒是將各類運(yùn)行參數(shù)監(jiān)測(cè)的傳感模塊、數(shù)據(jù)傳輸模塊、供電模塊與已有間隔棒高度集成的輸電線路在線監(jiān)測(cè)產(chǎn)品之一。

在傳感電氣集成網(wǎng)絡(luò)中，數(shù)據(jù)傳輸通常具有突發(fā)性，同時(shí)面臨傳輸環(huán)境造成的不可靠性，因此要以盡可能高的速率在短時(shí)間內(nèi)完成大量信息的傳輸，需要在網(wǎng)絡(luò)協(xié)議和軟件控制上采取負(fù)載均衡機(jī)制，提高多徑衰落條件下的傳輸性能和容量。均衡過程包括業(yè)務(wù)接入過程中的均衡和保持過程中的均衡：業(yè)務(wù)接入過程主要考慮無線資源管理連接的建立以及無線接入承載指派過程；業(yè)務(wù)保持過程主要考慮的切換過程的均衡，需要根據(jù)傳輸鏈路統(tǒng)計(jì)分析節(jié)點(diǎn)在網(wǎng)絡(luò)中所處的地位以及在保證網(wǎng)絡(luò)數(shù)據(jù)流量的穩(wěn)定性、可靠性及實(shí)時(shí)性的情況下，針對(duì)網(wǎng)內(nèi)數(shù)據(jù)傳輸具有的非均勻性，設(shè)計(jì)負(fù)載均衡的網(wǎng)絡(luò)地址轉(zhuǎn)換策略。在無線傳感器網(wǎng)絡(luò)的特定范圍內(nèi)分布有許多傳感器節(jié)點(diǎn)，由于多跳路由和多對(duì)一的數(shù)據(jù)流量模式，匯聚節(jié)點(diǎn)和匯聚節(jié)點(diǎn)相鄰的節(jié)點(diǎn)需要消耗更多的能量進(jìn)行數(shù)據(jù)的轉(zhuǎn)發(fā)，這樣使得它們的能量消耗速度遠(yuǎn)遠(yuǎn)超過其他部分的傳感器節(jié)點(diǎn)[1-4]。

消耗較少的能源得到較多的信息是傳感器網(wǎng)絡(luò)節(jié)能的目的。分簇機(jī)制不僅能夠通過分層的方式有效對(duì)傳感器節(jié)點(diǎn)進(jìn)行管理，而且能夠減少節(jié)點(diǎn)傳輸過程中的能量消耗，具有拓?fù)涔芾矸奖恪?shù)據(jù)融合簡(jiǎn)單等優(yōu)點(diǎn)，是當(dāng)前傳感器網(wǎng)絡(luò)重點(diǎn)研究的一種路由技術(shù)。

文獻(xiàn)[5]提出了一種Low Energy Adaptive Clustering Hierarchy（LEACH）算法協(xié)議,在LEACH 中，在從節(jié)點(diǎn)中選擇簇頭時(shí)未考慮節(jié)點(diǎn)剩余電量和到數(shù)據(jù)接收器的距離，因此節(jié)點(diǎn)在向簇頭或是數(shù)據(jù)接收器傳送數(shù)據(jù)時(shí)消耗了更多的能量。文獻(xiàn)[6]提出了一種LEACH 的擴(kuò)展版本（EECS），該文基于剩余能源選擇一些候選節(jié)點(diǎn)用于簇頭選擇，EECS 將簇頭分布在網(wǎng)絡(luò)中，較之LEACH 算法延長(zhǎng)網(wǎng)絡(luò)生命周期在35%以上，仍不是十分理想。文獻(xiàn)[7]介紹了Hybrid Energy-Efficient Distributed（HEED）協(xié)議，簇頭節(jié)點(diǎn)的選擇是基于節(jié)點(diǎn)的剩余電量及節(jié)點(diǎn)到其相鄰節(jié)點(diǎn)的距離。HEED 算法為了減少節(jié)點(diǎn)尤其是簇頭節(jié)點(diǎn)更高的能量損失增大了集群成員數(shù)量，定期觸發(fā)集群建立過程。但HEED 算法存在一個(gè)嚴(yán)重問題：靠近簇頭節(jié)點(diǎn)的數(shù)據(jù)接收器會(huì)因?yàn)橥ㄐ砰_銷提前耗盡電量。文獻(xiàn)[8]提出了基于權(quán)重的多跳，集群內(nèi)通信算法稱為基于分布權(quán)重的能量效率分層聚類（DWEHC）。其中，節(jié)點(diǎn)計(jì)算其對(duì)殘余能量的權(quán)重和與到它們相鄰節(jié)點(diǎn)的距離，鄰域中的最大加權(quán)節(jié)點(diǎn)被選為簇頭。DWEHC 在整個(gè)網(wǎng)絡(luò)中極好地分布節(jié)點(diǎn)能量消耗，但是節(jié)點(diǎn)因?yàn)榈退惴ǖ闹匦戮垲愡^程也產(chǎn)生了大量的控制消息開銷。類似于DWEHC，一個(gè)集中的節(jié)能路由體系結(jié)構(gòu)（ECRA）具有均勻密度的無線傳感器網(wǎng)絡(luò)分簇算法中在[9]中提出。ECRA 通過使用k-均值聚類算法完成聚類過程，保持理想的聚類分布，網(wǎng)絡(luò)集群使用K均值聚類法和簇頭選擇該算法完成了網(wǎng)絡(luò)的全部數(shù)據(jù)傳輸后，會(huì)重新構(gòu)造簇結(jié)構(gòu)。在ECRA 中，節(jié)點(diǎn)能量消耗明顯減少并在節(jié)點(diǎn)之間獨(dú)立分布。

本文旨在研究適用于輸電線路智能間隔棒的無線傳感器網(wǎng)絡(luò)體系結(jié)構(gòu)中網(wǎng)絡(luò)層的路由技術(shù)，對(duì)網(wǎng)絡(luò)能源負(fù)載平衡算法進(jìn)行改進(jìn)。本文提出了一種針對(duì)傳感網(wǎng)的雙層節(jié)能分簇算法，建立兩層集群來平衡傳感器的能源負(fù)載，對(duì)主集群使用K-均值集群方法，而對(duì)子集群通過角色成員關(guān)系建模尋找簇頭節(jié)點(diǎn)的能源補(bǔ)救措施。仿真結(jié)果證明，新提出的兩級(jí)集群高效節(jié)能的分簇算法可以有效地延長(zhǎng)網(wǎng)絡(luò)生命周期。

1 分簇算法

目前在無線傳感器網(wǎng)絡(luò)中典型的分簇算法主要有LEACH（Low2 Energy Adaptive Clustering Hierarchy） 算 法 和HEED(A Hybrid, Energy-Efficient Distributed clustering approach)算法等。

1.1 隨機(jī)選擇簇頭的LEACH算法

LEACH 是最典型的無線傳感器網(wǎng)絡(luò)分簇算法之一，由MIT 的學(xué)者W.R Heinzelman 等人首次提出，是一種基于簇類結(jié)構(gòu)的分層技術(shù)協(xié)議。

LEACH 算法簇頭選擇分為以下兩步：

1.1.1 周期進(jìn)行

LEACH 的運(yùn)作以“輪”來實(shí)現(xiàn)，每一輪周期由“設(shè)置”和“穩(wěn)定”這兩個(gè)階段構(gòu)成。每一輪的設(shè)置階段都需要隨機(jī)進(jìn)行簇頭和集群成員簇的構(gòu)造。

1.1.2 隨機(jī)選擇

簇頭的選取，將由對(duì)所有的節(jié)點(diǎn)產(chǎn)生的由0 到1 的隨機(jī)數(shù)決定。如果數(shù)值小于閾值 ，則該節(jié)點(diǎn)將當(dāng)選為當(dāng)前周期的簇頭節(jié)點(diǎn)。

閾值的表達(dá)式為：

其中P 為節(jié)點(diǎn)當(dāng)選為簇頭的概率，r 為當(dāng)前周期循環(huán)的次數(shù)，G 為在1/P 輪未成為簇頭節(jié)點(diǎn)的集合，En_current表示節(jié)點(diǎn)的當(dāng)前能量，En_max表示節(jié)點(diǎn)的初始能量，rs表示節(jié)點(diǎn)沒有成為簇頭的連續(xù)循環(huán)次數(shù)。

1.2 主次參數(shù)的HEED算法

HEED 算法以剩余能量和簇內(nèi)的通信耗能這兩個(gè)參數(shù)計(jì)算出節(jié)點(diǎn)成為簇頭的概率[10]。剩余能量為主參數(shù)。與此同時(shí)，HEED 算法定義了平均最小可達(dá)能量（Average Minimum Reachability Power， 簡(jiǎn)稱：AMRP）。AMRP 表達(dá)為：

圖1：總傳輸數(shù)據(jù)流的對(duì)比

圖2：生存節(jié)點(diǎn)與生命周期的對(duì)比

圖3：節(jié)點(diǎn)總能耗和通信數(shù)據(jù)流量對(duì)比圖

其中M 為簇內(nèi)節(jié)點(diǎn)的數(shù)量，minP 為最小能耗級(jí)別。

HEED 算法主要分為三個(gè)階段：初始階段，循環(huán)階段和最終階段。

1.2.1 初始階段

在初始階段，首先設(shè)置節(jié)點(diǎn)成為簇頭的初始概率，初始概率隨著網(wǎng)絡(luò)運(yùn)行和節(jié)點(diǎn)的剩余能量發(fā)生改變，成為節(jié)點(diǎn)被選作簇頭的最終概率 。

1.2.2 循環(huán)階段

在循環(huán)階段中，在簇內(nèi)循環(huán)尋找最小傳輸能量通信的節(jié)點(diǎn)作為簇頭節(jié)點(diǎn)。每次循環(huán)過程結(jié)束之后，將節(jié)點(diǎn)的乘以2，在進(jìn)入下一次循環(huán)。依此類推，直到找到簇頭節(jié)點(diǎn)之后中止循環(huán)。

1.2.3 最終階段

在最終階段，每個(gè)節(jié)點(diǎn)決定其最終的狀態(tài)，選擇簇頭并加入該簇。若節(jié)點(diǎn)為孤立節(jié)點(diǎn)，則申明該節(jié)點(diǎn)為簇頭節(jié)點(diǎn)。

1.3 算法分析

LEACH 算法實(shí)現(xiàn)了對(duì)分層無線傳感器網(wǎng)絡(luò)數(shù)據(jù)的傳輸管理，并且在選取簇頭時(shí)考慮了節(jié)點(diǎn)的剩余能量，但該算法在每一周期的開始階段都需要重新構(gòu)造簇，簇頭能量的開銷十分巨大，并且離散式區(qū)域算法無法做到最優(yōu)，位置較遠(yuǎn)的簇頭節(jié)點(diǎn)會(huì)因長(zhǎng)距離傳輸提前耗盡能力。HEED 算法不僅考慮了節(jié)點(diǎn)剩余能量，而且還考慮了簇內(nèi)的通信消耗，在一定程度上保證了節(jié)點(diǎn)的能耗負(fù)載平衡。然而同樣在每一輪都要消耗能量進(jìn)行簇頭的選擇，而且簇內(nèi)節(jié)點(diǎn)相對(duì)固定，沒有考慮中繼節(jié)點(diǎn)的剩余能量問題。在這種分層多對(duì)一的傳輸過程中，還是容易形成“能量洞”的問題。

2 模型建立

傳感器節(jié)點(diǎn)最主要的功能是數(shù)據(jù)的采集及其向基站進(jìn)行的轉(zhuǎn)發(fā)，但隨著傳感器數(shù)量的增多，監(jiān)測(cè)空間范圍的擴(kuò)大，數(shù)據(jù)包的路由會(huì)更加復(fù)雜，直接影響到節(jié)點(diǎn)的能耗[11]。而且，無線傳感器網(wǎng)絡(luò)中的高密度節(jié)點(diǎn)造成了數(shù)據(jù)的高冗余度，網(wǎng)絡(luò)對(duì)冗余數(shù)據(jù)的處理會(huì)嚴(yán)重縮短生命周期。對(duì)網(wǎng)絡(luò)進(jìn)行集群是對(duì)及節(jié)點(diǎn)進(jìn)行高效節(jié)能和減少數(shù)據(jù)冗余的有效路由手段。因此，需要設(shè)計(jì)一種高效節(jié)能容錯(cuò)嵌套的集群算法對(duì)能源負(fù)載進(jìn)行平衡，這對(duì)延長(zhǎng)無線傳感器網(wǎng)絡(luò)的生命周期至關(guān)重要。

2.1 模型簡(jiǎn)化

首先對(duì)新建立的網(wǎng)絡(luò)模型提出下列假設(shè)：

（1）第n 個(gè)能量約束均勻傳感器節(jié)點(diǎn)被部署在兼容密度為L(zhǎng)*L 的二維區(qū)域內(nèi)；

（2）數(shù)據(jù)接收器或基站位于部署區(qū)域的中心，具有無限的電源；

（3）所有節(jié)點(diǎn)都配備有獨(dú)立的電源，且初始電量相同；

（4）節(jié)點(diǎn)的傳輸范圍可以根據(jù)需要的通信距離進(jìn)行動(dòng)態(tài)調(diào)整。同時(shí)，假設(shè)節(jié)點(diǎn)都可以與數(shù)據(jù)接收器直接通信；

（5）如果兩個(gè)節(jié)點(diǎn)被告知是鄰居節(jié)點(diǎn)，則它們一定在彼此的傳輸范圍內(nèi)；

（6）節(jié)點(diǎn)不知道本身的位置信息，但它根據(jù)接收信號(hào)強(qiáng)度指標(biāo)可以獲知到鄰居節(jié)點(diǎn)的近似距離；

（7）收集到的數(shù)據(jù)可以被簇頭壓縮合并成單一的數(shù)據(jù)包簇頭。

2.2 模型建立

本文使用一階無線模型。無線電發(fā)射機(jī)和接收機(jī)電路能量損耗為發(fā)射放大器在自由空間(εfs)傳播模型中的損耗10pJ/bit/m2，雙射線(εpm)模型中的為0.013pJ/bit/m4。同時(shí)假設(shè)在自由傳播空間和雙射線空間中的路徑損耗分別為r2和r4。因此，在距離為d 的鏈路上傳播lbits 數(shù)據(jù)，消耗的能量為：

接收這些消息，消耗的能量為：

3 算法設(shè)計(jì)

使用k-均值聚類算法可以將給定的傳感器節(jié)點(diǎn)劃分成固定數(shù)量的集群。HEED 算法基于節(jié)點(diǎn)的剩余能量和簇間通信代價(jià)兩個(gè)參數(shù)的比值來增加節(jié)點(diǎn)被選做匯聚節(jié)點(diǎn)的概率，從而進(jìn)行周期性地選擇簇頭。我們?cè)趉-均值聚類算法和改進(jìn)的基于角色成員關(guān)系HEED算法的基礎(chǔ)上提出了雙層集群節(jié)能分簇算法。此算法分為確定主集群和子集群兩個(gè)階段。首先應(yīng)用改進(jìn)的k-均值聚類算法將網(wǎng)絡(luò)區(qū)域劃分為一定數(shù)量的主集群。之后應(yīng)用改進(jìn)的基于角色成員關(guān)系的分簇算法將確定子集群的簇頭并將每個(gè)主集群劃分成一定數(shù)量的子集群。子集群中確定的簇頭可以收集集群中其他節(jié)點(diǎn)的數(shù)據(jù)。主集群中確定的簇頭可以匯總簇頭的數(shù)據(jù)，并將數(shù)據(jù)傳輸?shù)交尽?/p>

算法如 Algorithm 1。

首先使用改進(jìn)的k-均值聚類算法根據(jù)節(jié)點(diǎn)的剩余能量將網(wǎng)絡(luò)區(qū)域劃分成Km個(gè)集群。主集群Km的數(shù)量通過下式確定：

其中M 是部署區(qū)域的面積，R 是節(jié)點(diǎn)的傳輸距離，X 是兩個(gè)簇頭之間的最大距離。分母是通過改進(jìn)算法得到的各個(gè)集群的覆蓋面積。算法聚類處理之后，一組節(jié)點(diǎn)被選作簇頭，用于主集群的通信。之后將每個(gè)主集群劃分成一定數(shù)量的子集群。群劃分成一定數(shù)量的子集群。

之后應(yīng)用改進(jìn)的基于角色成員關(guān)系的分簇算法將每個(gè)主集群劃分為一定數(shù)量的子集群，以節(jié)點(diǎn)的剩余能量和通信代價(jià)兩個(gè)參數(shù)作為依據(jù)，確定子集群中節(jié)點(diǎn)的角色關(guān)系和成員關(guān)系。

節(jié)點(diǎn)的初始化概率根據(jù)下面的公式確定：

Cprob是成為匯聚點(diǎn)的初始概率，CHprob是通過能源消耗的比例和通信代價(jià)這兩個(gè)參數(shù)得到該點(diǎn)成為匯聚點(diǎn)的最終概率。

定義兩個(gè)參數(shù)the_role 和is_belong。the_role 為傳感器的角色關(guān)系信息，is_belong 是節(jié)點(diǎn)的成員關(guān)系信息，在算法開始運(yùn)行之前將所有節(jié)點(diǎn)看成非成員關(guān)系。根據(jù)傳感器節(jié)點(diǎn)的鄰節(jié)點(diǎn)關(guān)系形成集合Snbr，Sgroup 將傳輸范圍radius 內(nèi)的Snbr 構(gòu)成一個(gè)初始的成員組。然后通過CHprob循環(huán)尋找組內(nèi)合適的匯聚節(jié)點(diǎn)和中繼節(jié)點(diǎn)。確定匯聚節(jié)點(diǎn)后，通過is_sink_msg（Node ID，final_sink，cost）消息將信息發(fā)送給所有的成員節(jié)點(diǎn)，同時(shí)確定其角色為匯聚點(diǎn)。而匯聚點(diǎn)的鄰節(jié)點(diǎn)可以作為備用匯聚節(jié)點(diǎn)，同時(shí)匯聚節(jié)點(diǎn)的鄰節(jié)點(diǎn)又扮演著中繼點(diǎn)的角色。源節(jié)點(diǎn)可以收到一個(gè)或者多個(gè)匯聚節(jié)點(diǎn)發(fā)送的信息，節(jié)點(diǎn)可以根據(jù)關(guān)系程度rational_sink（Ssink-radius）來選擇合適的匯聚節(jié)點(diǎn)，并加入該匯聚點(diǎn)的成員組，通過匯聚節(jié)點(diǎn)的is_sink_msg（Node ID, final_sink，cost）和源節(jié)點(diǎn)回應(yīng)的is_member_msg（Node ID, final_sink, cost）確定其成員關(guān)系。如果該節(jié)點(diǎn)已經(jīng)是某個(gè)成員組的源節(jié)點(diǎn)，當(dāng)匯聚點(diǎn)發(fā)生變化時(shí)，可以通過join_group（Node ID, final_sink, cost）選擇合適的成員關(guān)系。

4 仿真結(jié)果

本文利用MATLAB 軟件進(jìn)行仿真，仿真環(huán)境為1000*1000 的網(wǎng)絡(luò)大小，其中節(jié)點(diǎn)個(gè)數(shù)為1000 個(gè)。仿真起始時(shí)各節(jié)點(diǎn)處于相同的基礎(chǔ)能量，仿真過程中各節(jié)點(diǎn)遵循相同的消耗的能量損耗模型。算法的性能將從仿真結(jié)果的運(yùn)行生命周期和通信數(shù)據(jù)流量進(jìn)行分析，并與現(xiàn)有的LEACH 算法和HEED 算法進(jìn)行對(duì)比。

圖1 是相同起始能量下，不同算法間總數(shù)據(jù)流量的對(duì)比圖。從圖中可見，隨著仿真次數(shù)的增加，本文的雙層集群節(jié)能分簇算法傳輸?shù)目倲?shù)據(jù)流量保持相對(duì)的穩(wěn)定；與LEACH 和HEED 兩種算法相比較，雙層集群節(jié)能分簇算法在能量相等的前提下，具有更高的數(shù)據(jù)流量。

圖2 是相同起始能量下，生存節(jié)點(diǎn)數(shù)量隨時(shí)間變化圖，其反映了整個(gè)傳感網(wǎng)絡(luò)的壽命。對(duì)比其余兩種算法，可見在相同生命周期時(shí)，雙層集群節(jié)能分簇算法生存節(jié)點(diǎn)數(shù)量較多；節(jié)點(diǎn)能量全部耗盡時(shí)，雙層集群節(jié)能分簇算法生存周期最長(zhǎng)，即整體網(wǎng)絡(luò)壽命最長(zhǎng)，表明本文的算法均衡各節(jié)點(diǎn)間能量提升了節(jié)點(diǎn)能量使用效率。

圖3 反映了節(jié)點(diǎn)總能耗與通信數(shù)據(jù)流量間的關(guān)系。由圖可見，在相同的通信數(shù)據(jù)流量下，雙層集群節(jié)能分簇算法節(jié)點(diǎn)總能耗明顯小于其他兩種算法，整體節(jié)能效果明顯。

從仿真結(jié)果可以獲知，LEACH 算法由于只考慮了簇頭節(jié)點(diǎn)的能源消耗，并未考慮到簇內(nèi)節(jié)點(diǎn)消耗的不均勻。而HEED 算法是通過相鄰節(jié)點(diǎn)去分擔(dān)簇頭節(jié)點(diǎn)的負(fù)載，但是負(fù)載總量還是相對(duì)集中，能量消耗并不均勻。雙層集群節(jié)能分簇算法通過分布式的雙層數(shù)據(jù)聚合的方式，減小節(jié)點(diǎn)的傳輸范圍，從而使節(jié)點(diǎn)間的能耗負(fù)載均勻分布于各節(jié)點(diǎn)，最終提升傳感網(wǎng)絡(luò)的整體壽命。

5 結(jié)語(yǔ)

本文深入研究了無線傳感網(wǎng)在智能電網(wǎng)中的應(yīng)用特點(diǎn)，針對(duì)數(shù)據(jù)傳輸?shù)耐话l(fā)性，傳輸環(huán)境的不可靠性，和整個(gè)無線傳感網(wǎng)絡(luò)的能耗問題，提出了雙層集群節(jié)能分簇算法（DCES）。該分簇算法結(jié)合k-均值聚類的思想和基于角色成員關(guān)系的思想，以節(jié)點(diǎn)的剩余能量和簇間通信代價(jià)兩個(gè)參數(shù)作為依據(jù)進(jìn)行傳感器節(jié)點(diǎn)的聚類和簇頭的選擇。最后，通過MATLAB 仿真平臺(tái)對(duì)該算法進(jìn)行仿真。仿真結(jié)果表明，相較于其他分簇算法，本文提出的雙層集群節(jié)能分簇算法對(duì)傳感網(wǎng)絡(luò)構(gòu)建雙層集群，減小了節(jié)點(diǎn)的傳輸范圍，實(shí)現(xiàn)了節(jié)點(diǎn)之間的負(fù)載均衡，延長(zhǎng)了網(wǎng)絡(luò)的壽命。后續(xù)的研究中我們將擴(kuò)大該算法的適用范圍，提升此算法在大規(guī)模網(wǎng)絡(luò)中的性能，將其應(yīng)用于更復(fù)雜的場(chǎng)景，并在實(shí)際場(chǎng)景中進(jìn)行測(cè)試。