杜佳軒　楊軍

摘要：傳統(tǒng)分簇路由協(xié)議存在簇首節(jié)點(diǎn)的能耗分布不均勻，簇首節(jié)點(diǎn)與基站之間數(shù)據(jù)傳輸未采用最短路徑傳送，數(shù)據(jù)傳輸效率低使得網(wǎng)絡(luò)能耗較高及網(wǎng)絡(luò)生存期短問(wèn)題。針對(duì)這些問(wèn)題提出一種基于剩余能量和簇首最佳距離的分布式分簇路由算法EDAC。由基站根據(jù)剩余能量選擇候選簇頭，被選擇簇頭之間的距離要求在最佳簇首分布距離內(nèi)，利用蟻群優(yōu)化算法在各簇頭之間找到一條最短路徑多跳傳輸數(shù)據(jù)。Matlab仿真結(jié)果表明，EDAC協(xié)議比LEACH協(xié)議在網(wǎng)絡(luò)生存期上延長(zhǎng)了20%。

關(guān)鍵詞：無(wú)線傳感器網(wǎng)絡(luò)；剩余能量；最佳簇首分布；蟻群算法

中圖分類號(hào)：TP393.1 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1009-3044（2016）18-0025-02

Research of Clustering Routing Protocol based on Energy Efficient Wireless Sensor Network

DU Jia-xuan1，YANG Jun

（1.School of Mathematics and Computer， NingXia University，Yinchuan 750021，China； 2.Network Administration Center， NingXia University，Yinchuan 750021，China）

Abstract：Traditional cluster-based routing protocols do not perform so well in network energy consumption and lifetime when the network is large，because energy consumption among cluster-heads are not uniform，the route between BS and cluster-heads may be not the shortest，the low data transmission efficiency.To solve these problems， based on residual energy and the best distance of the cluster head proposed a distributed clustering routing protocols EDAC. The base station selects a candidate cluster head based on the residual energy ， to be selected cluster head should within the best cluster head distribution optimum distance， using AC algorithm find the shortest path between each cluster head so that multihop transmission data. The simulation with MATLAB shows that the EDAC outperforms LEACH nearly 20% in the network lifetime.

Key words： WSNs；Residual Energy；Best Cluster Head Distribution；AC

1 引言

無(wú)線傳感器網(wǎng)絡(luò)WSNs[1]（Wireless Sensor Networks）是數(shù)目較大且具有計(jì)算能力和處理能力小型傳感器節(jié)點(diǎn)通過(guò)有限的能量供應(yīng)進(jìn)行數(shù)據(jù)采集的自組織網(wǎng)絡(luò)。在有限的能量供應(yīng)下，傳感器節(jié)點(diǎn)將采集的感知數(shù)據(jù)通過(guò)某種協(xié)議傳送至基站，在這一過(guò)程中能量的有效利用是延長(zhǎng)無(wú)線傳感器網(wǎng)絡(luò)生存時(shí)間的關(guān)鍵。學(xué)者們針對(duì)WSNs中能量有效利用問(wèn)題提出了很多新穎的想法，其中分簇思想由于在實(shí)際應(yīng)用中得到了良好的效果從而引起了學(xué)者們的廣泛關(guān)注。LEACH（Low energy adaptive clustering hierarchy）[2]協(xié)議采取隨機(jī)性的選擇簇頭把能量的消耗分布在無(wú)線傳感器網(wǎng)絡(luò)內(nèi)的所有節(jié)點(diǎn)上。HEED[3]（Hybrid energy efficient distributed clustering）是基于混合能量和通信代價(jià)的特定概率公式選擇簇頭，剩余能量較高和低通信代價(jià)的節(jié)點(diǎn)才可以當(dāng)選簇頭，但是該協(xié)議不保證最優(yōu)的簇頭數(shù)和網(wǎng)絡(luò)連通性.

通過(guò)對(duì)以上文獻(xiàn)總結(jié)得出，已經(jīng)存在的算法都存在簇首分布不合理，簇間通信耗能較高，分簇不均勻等問(wèn)題。本文充分考慮了以上各算法的不足之處，主要針對(duì)各算法中簇頭分布不均勻，簇間數(shù)據(jù)傳輸能耗較大的問(wèn)題，提出一種綜合節(jié)點(diǎn)剩余能量又考慮簇頭分布、簇內(nèi)單跳簇間多跳分簇路由協(xié)議。

2 網(wǎng)絡(luò)模型和問(wèn)題描述

本文采用的無(wú)線電能耗模型，發(fā)送端的能量主要消耗在無(wú)線電發(fā)送元件和功率放大器，接收端的能量主要消耗在無(wú)線電發(fā)送元件，實(shí)驗(yàn)采用自由空間（功耗損失）多徑衰減（功耗損失）信道模型，主要與發(fā)送端和接收端之間的距離有關(guān)。

傳感器節(jié)點(diǎn)發(fā)送l-bit數(shù)據(jù)耗能：

（1）

傳感器節(jié)點(diǎn)接受1-bit數(shù)據(jù)耗能：

（2）

上式中，是發(fā)射電路元件功耗，為接收電路功耗，取決于數(shù)字編碼，過(guò)濾和信號(hào)擴(kuò)散方式。l是傳送的數(shù)據(jù)包的大小，d發(fā)送端和接收端之間的距離，和為放大器功耗，取決于接收者的距離和誤碼率。，為距離門限，根據(jù)數(shù)據(jù)發(fā)送者和接受者之間的距離，選擇自由空間信道模型或者多徑衰減信道模型。

3 改進(jìn)協(xié)議設(shè)計(jì)

改進(jìn)協(xié)議充分考慮了節(jié)點(diǎn)的剩余能量，與LEACH協(xié)議一致，本文也才用“輪”的概念。協(xié)議的沒輪分簇的建立和穩(wěn)定數(shù)據(jù)傳輸兩階段。在簇建立過(guò)程中，我們首先由基站指定簇頭，由于初始能量相同，在以后的輪中我們根據(jù)節(jié)點(diǎn)的剩余能量選擇候選簇頭，候選簇頭如果在簇首最佳距離之間，則候選簇頭成為正式簇頭，并廣播已當(dāng)選簇頭的消息，根據(jù)信號(hào)的質(zhì)量非簇頭就近入簇。本文利用基于能耗的最優(yōu)簇頭數(shù)公式來(lái)計(jì)算控制簇頭數(shù)量。在數(shù)據(jù)傳送階段，我們利用蟻群優(yōu)化算法在簇頭之間找出一條最短的數(shù)據(jù)傳送路徑，有效的減少網(wǎng)絡(luò)開銷。算法使用的變量如下：節(jié)點(diǎn)剩余能量：ND_R_Energy，節(jié)點(diǎn)平均剩余能量：ND_Ave_R_Energy，簇頭數(shù)目：k。

3.1 簇的建立

在簇頭選舉開始時(shí)，第一輪簇頭由基站指派。第二輪開始時(shí)每個(gè)簇統(tǒng)計(jì)簇內(nèi)節(jié)點(diǎn)的剩余能量信息，每個(gè)節(jié)點(diǎn)將自己的剩余能量發(fā)送給簇頭，各簇頭節(jié)點(diǎn)計(jì)算平均剩余能量，并且將計(jì)算所得結(jié)果傳送至基站，由基站計(jì)算整個(gè)網(wǎng)絡(luò)的平均剩余能量?；緩V播帶有平均剩余能量的消息，如果簇頭的剩余能量大于平均剩余能量則繼續(xù)當(dāng)選簇頭，否則進(jìn)行下一輪分簇。與由于簇頭的產(chǎn)生是均勻分布在網(wǎng)絡(luò)范圍內(nèi)的，從第三輪開始，在一個(gè)簇頭的管理范圍之內(nèi)，我們采取集中式簇頭選舉方式在每個(gè)簇范圍內(nèi)選舉簇頭，建立新的簇。如果沒有被任何簇加入，則自己發(fā)送廣播消息成為簇頭。具體算法步驟如下：

1）大于平均能量的傳感器節(jié)點(diǎn)放入集合A，并由大到小排序，即；

2）被當(dāng)做是第一個(gè)簇首，加入集合B中；

3）建立集合D，D是簇頭間距最佳距離范圍的集合。計(jì)算候選簇頭與的距離，并與集合D進(jìn)行比較，距離在集合D內(nèi)，則為簇首，加入簇首集合B中。否則，為普通節(jié)點(diǎn)；繼續(xù)計(jì)算下一個(gè)候選節(jié)點(diǎn)，繼續(xù)判斷，直到產(chǎn)生第二個(gè)簇首；

4）同理，在選擇第m（m>2）個(gè)簇頭時(shí)。必須保證它與前m-1個(gè)簇頭的距離都在D內(nèi)。

5）如果簇頭數(shù)達(dá)到計(jì)算得到的最優(yōu)簇頭數(shù)k，我們就停止本輪選舉過(guò)程。

6）通過(guò)以上的步驟我們可以得到集合，此后每個(gè)簇頭節(jié)點(diǎn)管理簇成員節(jié)點(diǎn)。

7）如果需要重新分簇，我們主要考慮節(jié)點(diǎn)的剩余能量，簇成員節(jié)點(diǎn)之間計(jì)算簇頭競(jìng)爭(zhēng)概率，概率最大者成為簇頭，并廣播自己成為簇頭消息，其他節(jié)點(diǎn)根據(jù)最小接收能量就近入簇，如果沒有被任何簇加入，則自己發(fā)送廣播消息成為簇頭。簇頭選舉概率由公式（8）給出

（8）

3.2 穩(wěn)定數(shù)據(jù)傳輸階段

分別將簇頭和基站的坐標(biāo)放入矩陣和中，利用蟻群優(yōu)化算法（AC）算法在簇頭和基站之間找到一條可行的最短路徑進(jìn)行數(shù)據(jù)傳輸[4]。為了避免數(shù)據(jù)傳輸集中于同一路徑，過(guò)早的消耗完此路徑上距離Sink節(jié)點(diǎn)較近節(jié)點(diǎn)的能量從而導(dǎo)致該節(jié)點(diǎn)失效，我們采取下面辦法：

程序流程

1）初始化：簇首和基站的總個(gè)數(shù)、簇首和基站坐標(biāo)、AC算法的相關(guān)參數(shù)；

2）基站運(yùn)行AC算法，得到一條最優(yōu)路徑并且記錄離Sink節(jié)點(diǎn)最近（n/4）節(jié)點(diǎn)的編號(hào)，計(jì)算這些節(jié)點(diǎn)的ND_R_Energy；

3）如果ND_R_Energy小于ND_Ave_R_Energy，將此節(jié)點(diǎn)加入AC算法的禁忌表，標(biāo)記為暫時(shí)不可傳輸節(jié)點(diǎn)。否則進(jìn)入第四步；

4）基站計(jì)算分析所得路徑是否可行，程序結(jié)束，節(jié)點(diǎn)開始數(shù)據(jù)傳送。否則，轉(zhuǎn)到第2步。

當(dāng)一輪數(shù)據(jù)傳輸結(jié)束后，重新進(jìn)入簇的建立階段，進(jìn)行下一輪簇重構(gòu)，直至能量耗盡。

4 仿真結(jié)果分析

4.1 仿真實(shí)驗(yàn)環(huán)境

本實(shí)驗(yàn)采用Matlab軟件進(jìn)行仿真分析，我們主要對(duì)LEACH協(xié)議及改進(jìn)的EDAC協(xié)議進(jìn)行了模擬，從網(wǎng)絡(luò)的死亡節(jié)點(diǎn)對(duì)比情況來(lái)進(jìn)行性能分析。實(shí)際仿真參數(shù)相同如下表1所示。

4.2 性能分析

我們分別運(yùn)行LEACH協(xié)議，EDAC協(xié)議10次，網(wǎng)絡(luò)中平均死亡節(jié)點(diǎn)（總結(jié)點(diǎn)-存活節(jié)點(diǎn)）對(duì)比情況如圖7所示，由對(duì)比可知EDAC協(xié)議第一個(gè)死亡節(jié)點(diǎn)出現(xiàn)要晚于LEACH協(xié)議（LEACH協(xié)議第一個(gè)節(jié)點(diǎn)死亡輪數(shù)是762，EDAC第一個(gè)節(jié)點(diǎn)死亡輪數(shù)為1050）。在死亡節(jié)點(diǎn)為80%時(shí)，LEACH協(xié)議運(yùn)行了大約1200輪，而EDAC協(xié)議已經(jīng)運(yùn)行了1500輪，從而EDAC協(xié)議使網(wǎng)絡(luò)生存期延長(zhǎng)了20%。實(shí)驗(yàn)表明，EDAC協(xié)議有效延長(zhǎng)了網(wǎng)絡(luò)中第一個(gè)死亡節(jié)點(diǎn)出現(xiàn)的時(shí)間，而且在網(wǎng)絡(luò)有效的情況下，改進(jìn)算法明顯延長(zhǎng)了網(wǎng)絡(luò)的生命周期，最終有效提高了網(wǎng)絡(luò)的性能。

參考文獻(xiàn)：

[1] Rashid B， Rehmani MH. Applications of wireless sensor networks for urban areas： A survey[J]. Journal of Network and Computer Applications， 2016， 60： 192-219.

[2] Arora VK， Sharma V， Sachdeva M. A Survey on LEACH and others Routing Protocols in Wireless Sensor Network[J]. Optik - International Journal for Light and Electron Optics.

[3] Chand S， Singh S， Kumar B. Heterogeneous HEED Protocol for Wireless Sensor Networks[J]. Wireless Personal Communications， 2014， 77 （3）： 2117-2139.

[4] 繆聰聰， 陳慶奎， 曹劍煒 等. 基于蟻群的無(wú)線傳感器網(wǎng)絡(luò)能量均衡非均勻分簇路由算法[J]. 計(jì)算機(jī)應(yīng)用， 2013，（12）： 3410-3414.