An Uneven Cluster Routing Algorithm Based Weight*

QIAO Xuegong，WANG Zhe，WANG Huaqian，GAO Shaobin

(1.College of Information Engineering，Taiyuan University of Technology，Taiyuan 030024，China; 2.School of Physical Science and Electronics，Shanxi Datong University，Datong Shanxi037009，China; 3.College of Electrical and Power Engineering Taiyuan University of Technology，Taiyuan 030024，China)

An Uneven Cluster Routing Algorithm Based Weight*

QIAO Xuegong1*，WANG Zhe2，WANG Huaqian3，GAO Shaobin1

(1.College of Information Engineering，Taiyuan University of Technology，Taiyuan 030024，China; 2.School of Physical Science and Electronics，Shanxi Datong University，Datong Shanxi037009，China; 3.College of Electrical and Power Engineering Taiyuan University of Technology，Taiyuan 030024，China)

Note energy limitation is the crucial point in communication protocols ofwireless sensor networks.It’s important to improve the nodes energy efficiency.Proposed an uneven Cluster routing algorithm(UCPA)based on Weight.The new local cluster head is selected according to theweight.And the new local head constructs its cluster with its own size according to the distance information.The data is transferred in chains from members to the head，and in dynamicmulti－h(huán)ops from cluster－h(huán)eads to base station.Simulation results show that this new algorithm effectively reduces network energy consumption，and can balance the energy consumption of network and better reduce the impacts of the"hot spots"and the network lifetime is prolonged obviously.

wireless sensor networks;weight;uneven clustering;chain structure;multi－h(huán)op

無線傳感器網(wǎng)絡(luò)是由大量部署于監(jiān)測區(qū)域內(nèi)靜止或移動(dòng)的微型傳感器節(jié)點(diǎn)以自組織形式構(gòu)成的，其主要目的是以協(xié)作的方式實(shí)現(xiàn)對覆蓋地理區(qū)域內(nèi)被測對象信息數(shù)據(jù)的感知、采集、處理和網(wǎng)絡(luò)傳輸［1］。通常運(yùn)行于人們不易接近的惡劣環(huán)境中，能源很難得到補(bǔ)充和替換，因此，設(shè)計(jì)無線傳感器網(wǎng)絡(luò)通信路由協(xié)議的核心問題之一就是找到一種能量高效利用的策略降低全網(wǎng)能量消耗，延長網(wǎng)絡(luò)生命周期［2］。已有大量研究表明，采用基于分簇的路由策略能極大提高無線傳感器網(wǎng)絡(luò)的可擴(kuò)展性和延長其網(wǎng)絡(luò)生命周期。其中，LEACH［3］(Low Energy Adaptive Clustering Hierarchy)協(xié)議就是一種典型的分簇路由算法。在大部分分簇算法中傳感網(wǎng)絡(luò)都是周期性地選擇簇首，收集簇內(nèi)成員節(jié)點(diǎn)的傳感數(shù)據(jù)再經(jīng)數(shù)據(jù)融合后轉(zhuǎn)發(fā)至基站。這些算法中，簇內(nèi)數(shù)據(jù)收集、數(shù)據(jù)融合和與基站的通信通常都是由簇首節(jié)點(diǎn)單獨(dú)完成，這樣簇首節(jié)點(diǎn)容易因承當(dāng)過多任務(wù)而過早死亡，影響網(wǎng)絡(luò)的生命周期。文獻(xiàn)［4－8］在簇首與匯聚節(jié)點(diǎn)之間采取多跳的通信方式，有利于節(jié)約簇首能量。但是，崔莉［9］等認(rèn)為簇首間采用多跳的通信方式向基站傳送數(shù)據(jù)，會(huì)因離基站近的簇首節(jié)點(diǎn)需承擔(dān)大量轉(zhuǎn)發(fā)數(shù)據(jù)任務(wù)而形成“熱區(qū)”問題，簇首節(jié)點(diǎn)過快死亡。

本文在研究分簇路由協(xié)議如LEACH、EECS［10］(An Energy－Efficient Clustering Scheme)等的基礎(chǔ)上提出了一種基于權(quán)值的非均勻分簇路由算法。該算法綜合考慮網(wǎng)絡(luò)節(jié)點(diǎn)的剩余能量和區(qū)域節(jié)點(diǎn)的密集度計(jì)算競爭簇首權(quán)值，簇首再根據(jù)與基站的距離計(jì)算成簇半徑，使靠近基站簇的成簇半徑和簇內(nèi)節(jié)點(diǎn)數(shù)小于遠(yuǎn)離基站的簇，而簇首個(gè)數(shù)多于遠(yuǎn)離基站的區(qū)域，便于緩解“熱區(qū)”簇首節(jié)點(diǎn)能量過快消耗問題。簇內(nèi)成員以鏈?zhǔn)浇Y(jié)構(gòu)與簇首通信，這樣減少簇首節(jié)點(diǎn)收集和融合簇內(nèi)數(shù)據(jù)的能量消耗，使能量更均衡的分布在普通節(jié)點(diǎn)上，有效延長網(wǎng)絡(luò)生命周期。當(dāng)簇內(nèi)數(shù)據(jù)收集完畢后，簇首采用多跳的方式將數(shù)據(jù)傳送給基站，減少簇首與基站直接通信的次數(shù)，進(jìn)一步減輕簇首負(fù)擔(dān)。

1 系統(tǒng)模型

1.1 能耗模型

本文采用與文獻(xiàn)［11－13］相同的無線能耗模型，傳感器節(jié)點(diǎn)能耗可分為發(fā)射數(shù)據(jù)能耗、接收數(shù)據(jù)能耗和融合數(shù)據(jù)能耗。如下式(1)為發(fā)射k比特?cái)?shù)據(jù)到距離為d位置的能量損耗，此能耗由發(fā)射電路和功率放大電路消耗兩部分組成。功率放大能耗則根據(jù)發(fā)送節(jié)點(diǎn)和接收節(jié)點(diǎn)之間距離分別采用自由空間模型(d＜do)和多路徑衰減模型(d≥do)。

其中Eelec為發(fā)射電路消耗能量，εfs和εamp分別為兩種信道模型下功率放大電路所需能量。式(2)為接收k比特?cái)?shù)據(jù)能耗，僅由電路消耗引起。

假設(shè)鄰近節(jié)點(diǎn)采集的數(shù)據(jù)具有較高冗余度，每輪數(shù)據(jù)采集過程中每個(gè)節(jié)點(diǎn)將接收簇內(nèi)鄰近節(jié)點(diǎn)數(shù)據(jù)后再與本身節(jié)點(diǎn)收集數(shù)據(jù)融合成固定長度數(shù)據(jù)包再向下一節(jié)點(diǎn)發(fā)送，傳感器節(jié)點(diǎn)融合k比特?cái)?shù)據(jù)所消耗的能量EF為:

其中Eda表示融合1比特?cái)?shù)據(jù)所消耗的能量。

1.2 生存時(shí)間數(shù)學(xué)模型

無線傳感器網(wǎng)絡(luò)生存時(shí)間LT(Lifetime)采用有效數(shù)據(jù)采集輪數(shù)來描述

其中，μ是網(wǎng)絡(luò)能耗均值，ζ是衡量網(wǎng)絡(luò)能耗分布均勻性的函數(shù)。

2 算法

針對當(dāng)前層次路由協(xié)議中普遍存在網(wǎng)絡(luò)均衡性差和剩余能量小的節(jié)點(diǎn)可能充當(dāng)簇首的缺點(diǎn)，提出一種基于權(quán)值的非均勻分簇算法。

2.1 算法提出

簇首具有收集和傳輸數(shù)據(jù)的作用，因此能量消耗比較大。在節(jié)點(diǎn)密集程度越高區(qū)域剩余能量較大節(jié)點(diǎn)更容易成為候選簇首，成簇半徑與節(jié)點(diǎn)和基站距離有關(guān)，距離越近，成簇半徑越小，所分簇區(qū)域越多，因此在靠近基站區(qū)域中有更多簇首承擔(dān)轉(zhuǎn)發(fā)任務(wù)。該算法關(guān)鍵之處是簇的建立階段，在該階段要進(jìn)行最佳簇首的選擇，采用何種方法進(jìn)行簇首優(yōu)選是層次路由算法的核心。本文提出將節(jié)點(diǎn)剩余能量和區(qū)域節(jié)點(diǎn)密集程度作為傳感器節(jié)點(diǎn)選擇最佳簇首的指標(biāo)。在選擇簇首時(shí)，不僅要考慮到節(jié)點(diǎn)的剩余能量，還要考慮節(jié)點(diǎn)在充當(dāng)了簇首后消耗的能量和整個(gè)區(qū)域的平均剩余能量。在競爭簇首時(shí)當(dāng)節(jié)點(diǎn)剩余能量大時(shí)，表示有能力充當(dāng)簇首，競爭機(jī)會(huì)就大;當(dāng)節(jié)點(diǎn)密集時(shí)，在該區(qū)域形成簇的可能性增大，有利于減少節(jié)點(diǎn)向簇首傳輸數(shù)據(jù)消耗的能量和簇首收集數(shù)據(jù)消耗的能量。如果傳感器節(jié)點(diǎn)只接收到一個(gè)簇首節(jié)點(diǎn)競選消息，那么，向該節(jié)點(diǎn)發(fā)送加入消息;如果收到多個(gè)簇首節(jié)點(diǎn)競選消息，計(jì)算各個(gè)簇首權(quán)重，選擇權(quán)值大的節(jié)點(diǎn)作為簇首，向該節(jié)點(diǎn)發(fā)送加入消息，簇頭競爭公式如下:

其中Wci表示節(jié)點(diǎn)Ni競爭簇首的權(quán)值，Ei表示節(jié)點(diǎn)Ni的當(dāng)前剩余能量，Eint表示節(jié)點(diǎn)初始能量，Nnbr表示節(jié)點(diǎn)Ni鄰居節(jié)點(diǎn)個(gè)數(shù)，a為小于1的常數(shù)，經(jīng)過多次仿真，a為0.85時(shí)簇首選擇效果最好，后面仿真結(jié)果均是在此條件下進(jìn)行的，Kc是區(qū)域節(jié)點(diǎn)最優(yōu)簇首個(gè)數(shù)［14］。

n表示網(wǎng)絡(luò)中節(jié)點(diǎn)的總數(shù)，εfs和εamp分別表示當(dāng)功率放大損耗采用自由空間模型和多路徑衰減模型時(shí)所需要能量的消耗，M表示節(jié)點(diǎn)覆蓋區(qū)域的面積，dtoBs表示網(wǎng)絡(luò)覆蓋區(qū)域中心點(diǎn)到基站的距離。

UCRA算法在成簇時(shí)改變常規(guī)算法中簇半徑大小固定不變的方法，簇首根據(jù)本節(jié)點(diǎn)與基站距離來計(jì)算成簇半徑大小，使得靠近基站越近，形成的簇越小，從而確保距離基站近的簇首能耗降低，有效減少了“熱點(diǎn)”簇首的出現(xiàn)。成簇半徑定義如下:

其中Ri表示節(jié)點(diǎn)Ni競選簇首成簇半徑，Rc是常數(shù)，c在(0～1)取值，本文c取1/3，dmax表示區(qū)域中節(jié)點(diǎn)距基站的最遠(yuǎn)距離，dmin表示表示區(qū)域中節(jié)點(diǎn)距基站的最近距離，d(Ni，Bs)表示節(jié)點(diǎn)Ni到基站的距離。

在數(shù)據(jù)采集階段，簇首將簇內(nèi)成員連成一條數(shù)據(jù)傳輸鏈，簇成員在數(shù)據(jù)傳輸時(shí)以鏈?zhǔn)浇Y(jié)構(gòu)從鏈的兩端向簇首傳送數(shù)據(jù)，簇成員只需跟鄰近簇成員接收和發(fā)送數(shù)據(jù)各一次。假設(shè)在第a輪數(shù)據(jù)采集過程中，第i個(gè)簇有n個(gè)傳感器節(jié)點(diǎn)，每個(gè)傳感器節(jié)點(diǎn)每次采集K比特?cái)?shù)據(jù)，則簇首在此次數(shù)據(jù)采集過程中接收簇內(nèi)數(shù)據(jù)和融合數(shù)據(jù)能量消耗為:

按LEACH協(xié)議收集簇內(nèi)數(shù)據(jù)，簇首需接收n－1次簇內(nèi)非簇首節(jié)點(diǎn)傳送來的數(shù)據(jù)，能量消耗為:

由上式可知新算法與LEACH協(xié)議相比較，簇首在一次數(shù)據(jù)收集中節(jié)約能耗，由于簇內(nèi)成員節(jié)點(diǎn)數(shù)n?3，所以簇首在數(shù)據(jù)收集時(shí)的能耗將大大減少，有效平衡簇首和普通節(jié)點(diǎn)能耗。

2.2 算法描述

UCRA算法采用與LECH協(xié)議相似運(yùn)行機(jī)制，按輪運(yùn)行，與LEACH不同之處是LEACH協(xié)議每輪更換簇頭一次，UCRA算法更換簇首則根據(jù)網(wǎng)絡(luò)實(shí)際情況實(shí)時(shí)進(jìn)行變化，每輪分為簇建立階段、數(shù)據(jù)采集階段和簇重組階段。簇建立階段的關(guān)鍵是簇首選舉。傳感器節(jié)點(diǎn)內(nèi)設(shè)有定時(shí)系統(tǒng)，分簇算法定時(shí)被觸發(fā)，設(shè)經(jīng)過分簇時(shí)間Ts，接著進(jìn)入數(shù)據(jù)采集階段，設(shè)時(shí)間長度為Tw。此時(shí)第1次數(shù)據(jù)采集完成，進(jìn)入簇重組階段。時(shí)間按分配圖如圖1所示。

圖1 時(shí)間分配圖

在網(wǎng)絡(luò)部署階段，基站用一個(gè)給定發(fā)射功率向全網(wǎng)發(fā)送一廣播消息，每個(gè)節(jié)點(diǎn)根據(jù)接收到信號強(qiáng)弱計(jì)算節(jié)點(diǎn)自身到基站的近似距離，該距離是傳感器節(jié)點(diǎn)計(jì)算競選成簇半徑的重要信息。

為更好描述，對文中符號定義說明如下:

Node_nbr:鄰居節(jié)點(diǎn)集合，定義為以本節(jié)點(diǎn)為中心Rc為半徑的區(qū)域圓內(nèi)所有節(jié)點(diǎn)，初值為空。

Node_higher:在鄰居節(jié)點(diǎn)中權(quán)值比本節(jié)點(diǎn)高且未被覆蓋的存活節(jié)點(diǎn)集合，初值為空。Node_ch:鄰居節(jié)點(diǎn)中簇首節(jié)點(diǎn)集合，初值為空。Node_covered:在候選簇首節(jié)點(diǎn)中所覆蓋的鄰居節(jié)點(diǎn)集合，初值為空。

Node_next:保存?zhèn)鞲衅鞴?jié)點(diǎn)數(shù)據(jù)傳輸下一跳節(jié)點(diǎn)ID號。

is_covered:節(jié)點(diǎn)覆蓋標(biāo)志位，初值為零。“覆蓋”的定義為:Node_ch非空。

is_ch:候選簇首標(biāo)志位，初值為零。

簇建立階段，每個(gè)節(jié)點(diǎn)Node以固定半徑距離Rc廣播Node_messege，Node_messege消息包含本節(jié)點(diǎn)ID號和競爭簇首的權(quán)值信息。接著收集鄰居節(jié)點(diǎn)ID號存于Node_nbr集合中，并把鄰居節(jié)點(diǎn)競爭簇首權(quán)值大于本節(jié)點(diǎn)且兩節(jié)點(diǎn)距離小于競選半徑Ri的節(jié)點(diǎn)ID號存于Node_higher集合中。所有節(jié)點(diǎn)重復(fù)操作T1時(shí)間后，如果節(jié)點(diǎn)Node_higher集合仍為空，此時(shí)說明該節(jié)點(diǎn)競選半徑內(nèi)沒有競爭簇首的權(quán)值比自己大的節(jié)點(diǎn)，把競選半徑Ri區(qū)域內(nèi)所有節(jié)點(diǎn)ID號存于Node_covered中，該節(jié)點(diǎn)宣稱自己為簇首并以半徑Rc在簇內(nèi)廣播Head_message，is_covered和is_ch標(biāo)志位置1。其中Head_message消息包括本節(jié)點(diǎn)ID號和Node_covered集合信息。非簇首節(jié)點(diǎn)收到Head_message消息后將發(fā)送消息節(jié)點(diǎn)ID號和競爭簇首的權(quán)值信息存于Node_ch中并根據(jù)接收的Node_covered信息更新Node_higher集合。當(dāng)收到的Head_message中Node_covered信息包含自己ID號時(shí)，is_covered標(biāo)志位置1。若節(jié)點(diǎn)的Node_higher集合為空則以半徑Rc在簇內(nèi)廣播Head_message并重復(fù)上述消息處理過程。其算法執(zhí)行如下所示:

①N.is_head=flase

②N.is_covered=flase

③Broadcast Node_message(ID and Wci)

④On receiving Node_message(ID and Wci)from Ni

⑤If distance(Ni，Nj)＜Rc

⑥Add Nito Nj.Node_nbr

⑦If Wi＞W(wǎng)j

⑧Add Nito Nj.Node_higher

⑨End if

⑩End if

? Wait T1

? If N.Node_higher=empty

? N.is_head=true and N.is_covered=true

? End if

? While N.is_head=true then do

? If N.is_covered=flase

? Broadcast head_message(ID，Wci，N.Node_covered)

? N.is_covered=true

? End if

? On receiving head_message(ID，Wci，N.Node_covered from Ni

? Add Nito Nj.Node_ch

? If Nj?Ni.Node_covered

? Nj.is_covered=true

? End if

? Update Node_higher

? If N.Node_higher=empty

? N.is_head=true

? End if

? End While

在經(jīng)過時(shí)間T2(T1?T2)后簇選舉完成，非簇首節(jié)點(diǎn)選擇Node_ch集合中距離自己最近簇首節(jié)點(diǎn)發(fā)送一申請加簇JOIN消息。簇首節(jié)點(diǎn)接收非簇首節(jié)點(diǎn)JOIN消息完成后，將本簇內(nèi)所有成員節(jié)點(diǎn)連接成一條數(shù)據(jù)傳輸鏈。其具體實(shí)現(xiàn)方法為簇首根據(jù)簇內(nèi)成員離基站的距離遠(yuǎn)近對簇內(nèi)成員節(jié)點(diǎn)進(jìn)行排序處理，排序完成后節(jié)點(diǎn)的位置排列就為數(shù)據(jù)傳輸鏈的位置排列，即簇內(nèi)離基站最近簇成員節(jié)點(diǎn)為數(shù)據(jù)傳輸鏈的一端點(diǎn)，其他簇成員節(jié)點(diǎn)根據(jù)離基站從近到遠(yuǎn)依次為數(shù)據(jù)傳輸鏈的下一跳節(jié)點(diǎn)，離基站最遠(yuǎn)簇成員節(jié)點(diǎn)為數(shù)據(jù)傳輸鏈的另一端點(diǎn)。

簇首節(jié)點(diǎn)成鏈完成后以半徑Rc在簇內(nèi)向申請加入本簇成員節(jié)點(diǎn)廣播Cluster_chain消息，Cluster_ chain消息包括數(shù)據(jù)傳輸鏈節(jié)點(diǎn)的排列位置和簇內(nèi)成員節(jié)點(diǎn)的各TDMA時(shí)隙。非簇首節(jié)點(diǎn)接收到本簇首Cluster_chain消息后，從Cluster_chain消息中找到在數(shù)據(jù)傳輸鏈中自己的下一跳節(jié)點(diǎn)ID號并存于Node_next中。判斷簇首離基站的距離是否大于自己離基站的距離成為數(shù)據(jù)傳輸?shù)年P(guān)鍵之處，如果大于設(shè)置為True，Node_next保存的節(jié)點(diǎn)ID號為數(shù)據(jù)傳輸鏈中當(dāng)前節(jié)點(diǎn)下一跳節(jié)點(diǎn)ID號，否者保存的是數(shù)據(jù)傳輸鏈中當(dāng)前節(jié)點(diǎn)上一跳節(jié)點(diǎn)ID號。圖2為100個(gè)傳感器節(jié)點(diǎn)隨機(jī)分布于100×100區(qū)域內(nèi)的成簇結(jié)構(gòu)圖。

成簇完成后，所有簇首節(jié)點(diǎn)產(chǎn)生一棵以基站為根節(jié)點(diǎn)的路由樹。具體做法是:簇首節(jié)點(diǎn)以覆蓋半徑2Rc廣播Routing消息，Routing消息包含節(jié)點(diǎn)ID及權(quán)值，同時(shí)簇首收到Routing消息選擇Wi權(quán)值最小簇首節(jié)點(diǎn)作為父節(jié)點(diǎn)，否則，選擇基站作為自己的父節(jié)點(diǎn)，由此構(gòu)建一棵以基站為根節(jié)點(diǎn)的路由樹。Wi定義如下:

其中Eint表示為網(wǎng)絡(luò)傳感器節(jié)點(diǎn)初始能量，Eci表示為第i個(gè)簇首的當(dāng)前能量，d(Ni，Nj)代表簇首i到簇首j的距離，d(Nj，Bs)表示簇首j與基站的距離。圖3為簇首構(gòu)建的路由樹結(jié)構(gòu)示意圖。

圖3 路由樹構(gòu)建圖

數(shù)據(jù)采集階段，節(jié)點(diǎn)以簇為單位根據(jù)TDMA時(shí)隙將數(shù)據(jù)從鏈端開始向下一跳節(jié)點(diǎn)傳輸，最后送達(dá)簇首節(jié)點(diǎn)。當(dāng)節(jié)點(diǎn)接收到鄰居節(jié)點(diǎn)數(shù)據(jù)后，進(jìn)行數(shù)據(jù)壓縮和融合，減少數(shù)據(jù)發(fā)送數(shù)量以此降低能量消耗。簇首節(jié)點(diǎn)以多跳方式將數(shù)據(jù)傳送給基站，具體步驟是每個(gè)簇首節(jié)點(diǎn)將融合后數(shù)據(jù)發(fā)送到自己父節(jié)點(diǎn)，最后將數(shù)據(jù)送至路由樹的根節(jié)點(diǎn)即基站。

簇重組階段，UCRA算法每輪采集數(shù)據(jù)兩次后，再根據(jù)網(wǎng)絡(luò)實(shí)際情況更新簇首。簇首判斷自身節(jié)點(diǎn)能量是否大于簇內(nèi)節(jié)點(diǎn)平均能量Een，當(dāng)簇首節(jié)點(diǎn)能量大于Een時(shí)簇首繼續(xù)擔(dān)任簇首并在簇內(nèi)廣播RCluster_chain，否則，選擇簇內(nèi)成員中剩余能量最大者作為下一次數(shù)據(jù)采集簇首并廣播RCluster_ chain消息。RCluster_chain消息為下一次數(shù)據(jù)采集的簇首ID號。其中Een定義為:

其中n為簇內(nèi)成員節(jié)點(diǎn)個(gè)數(shù)，Ei表示為節(jié)點(diǎn)當(dāng)前剩余能量。

3 算法仿真與分析

為了測試UCRA算法性能，本文采用MATLAB對LEACH，EECS和UCRA進(jìn)行了仿真比較。

3.1 仿真環(huán)境

在實(shí)驗(yàn)中假設(shè)400個(gè)傳感器節(jié)點(diǎn)隨機(jī)分布于200 m×200 m的矩形區(qū)域內(nèi)，每個(gè)節(jié)點(diǎn)初使能量為0.5 J，Rc為40 m，基站位置設(shè)為(100，250)，數(shù)據(jù)包大小為2 000 kbit。下面是分別從系統(tǒng)生命周期、死亡節(jié)點(diǎn)對比輪數(shù)和網(wǎng)絡(luò)總體能耗進(jìn)行仿真比較。

3.2 仿真結(jié)果

圖4對各算法系統(tǒng)生命周期進(jìn)行比較，從圖4中可看出，UCRA第1個(gè)節(jié)點(diǎn)死亡的時(shí)間比LEACH和EECS都大大推遲，UCRA網(wǎng)絡(luò)生命周期比LEACH協(xié)議延長兩倍左右，比EECS延長約46%，這表明UCRA能有效延長網(wǎng)絡(luò)生命周期。

圖4 系統(tǒng)生命周期

從圖5中可看出，UCRA出現(xiàn)5%和50%死亡節(jié)點(diǎn)的時(shí)間比LEACH平均延遲一倍左右，比EECS平均延遲35%左右，這表明在相同網(wǎng)絡(luò)生存時(shí)間內(nèi)UCRA算法死亡節(jié)點(diǎn)數(shù)明顯少于LEACH和EECS。從圖6能耗圖中我們可發(fā)現(xiàn)UCRA能耗曲線明顯比LEACH和EECS平緩，這說明UCRA協(xié)議能耗效率更高，能更好均衡網(wǎng)絡(luò)節(jié)點(diǎn)能耗。

圖5 系統(tǒng)死亡節(jié)點(diǎn)對比

圖6 網(wǎng)絡(luò)總體能耗對比

4 結(jié)束語

本文所提出的基于鏈?zhǔn)絺鬏斀Y(jié)構(gòu)的非均勻分簇路由算法，其顯著特點(diǎn)有:1)簇首選舉采用基于權(quán)值的局部簇首競爭機(jī)制，這樣選出簇首有較好分散性，避免在同一區(qū)域存在多個(gè)簇首的現(xiàn)象;2)候選簇首采用非均勻成簇方式，靠近基站成簇半徑小且分區(qū)多，這樣靠近基站區(qū)域有更多簇首節(jié)點(diǎn)轉(zhuǎn)發(fā)數(shù)據(jù)，能有效地避免“熱點(diǎn)”問題的影響;3)簇內(nèi)成員采用鏈?zhǔn)浇Y(jié)構(gòu)向簇首傳送數(shù)據(jù)，在簇內(nèi)數(shù)據(jù)傳輸階段節(jié)點(diǎn)只需與離自己最近的節(jié)點(diǎn)進(jìn)行通信，所有節(jié)點(diǎn)只需接收和發(fā)送數(shù)據(jù)一次，能量消耗進(jìn)一步均勻分布在普通傳感器節(jié)點(diǎn)中;4)簇間數(shù)據(jù)傳輸采用多跳數(shù)據(jù)轉(zhuǎn)發(fā)，減少簇首直接與基站通信數(shù)量。本文在設(shè)計(jì)實(shí)驗(yàn)時(shí)都是假設(shè)在理想的通信環(huán)境中沒有過多考慮外界信號干擾及數(shù)據(jù)通信安全方面問題，下一步的工作，充分考慮以上因素后使該算法更適合在實(shí)際的傳感器網(wǎng)絡(luò)中應(yīng)用。

［1］王志良，王新平.物聯(lián)網(wǎng)工程實(shí)訓(xùn)教程［M］.北京:機(jī)械工業(yè)出版社，2011:3－5.

［2］唐勇，周明天，張欣.無線傳感器網(wǎng)絡(luò)路由協(xié)議研究進(jìn)展［J］.軟件學(xué)報(bào)，2006，17(3):410－421.

［3］Heinzelman W，Chandrakasan A，Balakrishnan H.Energy－Efficient Communication Protocol for Wireless Microsensor Networks［J］. IEEE Proceedings of the Hawaii Int’l Conf System Science，2000: 3005－3014.

［4］孫利民，李建中，陳渝.無線傳感器網(wǎng)絡(luò)［M］.北京:清華大學(xué)出版社，2005:94－100.

［5］劉慶，王培康.無線傳感器網(wǎng)絡(luò)的安全分簇路由協(xié)議［J］.計(jì)算機(jī)仿真，2009，26(4):167－171.

［6］陸立芳，閆建國.無線傳感器網(wǎng)絡(luò)路由協(xié)議的優(yōu)化設(shè)計(jì)［J］.計(jì)算機(jī)仿真，2010，27(12):125－128.

［7］張文祥，馬銀花，郭繼坤.無線傳感器網(wǎng)絡(luò)路由算法的研究［J］.計(jì)算機(jī)測量與控制，2009，17(3):617－619.

［8］童孟軍，關(guān)華丞.基于蟻群算法的能量均衡多路徑路由算法的研究［J］.傳感技術(shù)學(xué)報(bào)，2013，26(3):425－434.

［9］崔莉，鞠海玲，苗勇，等.無線傳感器網(wǎng)絡(luò)研究進(jìn)展［J］.計(jì)算機(jī)研究與發(fā)展，2005，42(1):163－174.

［10］李成法，陳貴海.一種基于非均勻分簇的無線傳感器網(wǎng)絡(luò)路由協(xié)議［J］.計(jì)算機(jī)學(xué)報(bào)，2007，30(1):88－91.

［11］孫建延，徐春香.無線傳感器網(wǎng)絡(luò)在油田數(shù)據(jù)傳輸系統(tǒng)中的應(yīng)用［J］.儀表技術(shù)與傳感器，2012(6):53－55.

［12］秦智超，周正，趙小川.利用粒子群優(yōu)化的WSN環(huán)狀簇路由協(xié)議［J］.北京郵電大學(xué)學(xué)報(bào)，2012，35(5):26－30.

［13］尚鳳軍，Mehran Abolhasan，Tadeusz Wysocki.無線傳感器網(wǎng)絡(luò)的分布式能量有效非均勻成簇算法［J］.通信學(xué)報(bào)，2009，30 (10):34－43.

［14］劉園莉，李臘元，盧迪.節(jié)能的無線傳感器網(wǎng)絡(luò)分簇路由協(xié)議的研究［J］.傳感器技術(shù)學(xué)報(bào)，2010，23(12):1792－1797.

喬學(xué)工(1968－)，女，漢族，山西太原人，副高/工學(xué)博士，碩士生導(dǎo)師。現(xiàn)工作在太原理工大學(xué)信息工程學(xué)院，主要研究領(lǐng)域?yàn)闊o線傳感器網(wǎng)絡(luò)、物聯(lián)網(wǎng)技術(shù)、智能控制等。已發(fā)表學(xué)術(shù)論文20余篇，EI收錄10余篇，qiaoxuegong@ tyut.edu.cn;

王哲(1992－)，男，漢族，山西大同大學(xué)，主要研究方向電子信息，無線傳感器網(wǎng)絡(luò);

高紹斌(1988－)男，漢族，碩士生，主要研究方向?yàn)闊o線傳感器網(wǎng)絡(luò)。

基于權(quán)值的非均勻分簇路由算法*

喬學(xué)工1*，王哲2，王華倩3，高紹斌1

(1.太原理工大學(xué)信息工程學(xué)院，太原030024;2.山西大同大學(xué)物理與電子科學(xué)學(xué)院，山西大同037009; 3.太原理工大學(xué)電氣與動(dòng)力工程學(xué)院，太原030024)

節(jié)點(diǎn)能量有限是無線傳感器網(wǎng)絡(luò)通信協(xié)議設(shè)計(jì)中的一個(gè)重要瓶頸，因此，在無線傳感器網(wǎng)絡(luò)中，考慮網(wǎng)絡(luò)節(jié)點(diǎn)能量的高效利用具有十分重要的理論和實(shí)際意義。因而，提出一種基于權(quán)值機(jī)制的非均勻分簇路由算法，該算法采用權(quán)值的局部競選簇首策略，簇首根據(jù)距離信息構(gòu)建大小不均的多個(gè)簇，簇成員節(jié)點(diǎn)以鏈?zhǔn)浇Y(jié)構(gòu)向簇首傳送數(shù)據(jù)，最后簇首采用多跳的方式向基站傳送數(shù)據(jù)。實(shí)驗(yàn)仿真結(jié)果表明，提出的新算法能有效地降低和均衡網(wǎng)絡(luò)節(jié)點(diǎn)能耗，改善“熱區(qū)”問題，顯著地延長網(wǎng)絡(luò)生命周期。

無線傳感器網(wǎng)絡(luò);權(quán)值;非均勻分簇;鏈?zhǔn)絺鬏斀Y(jié)構(gòu);多跳

TP393

A

1004－1699(2014)01－0107－06

2013－09－29修改日期:2013－12－30

C:6150P

10.3969/j.issn.1004－1699.2014.01.020

項(xiàng)目來源:山西省自然科學(xué)基金項(xiàng)目(2012011013－5);國家自然科學(xué)基金項(xiàng)目(51279122);山西省青年科學(xué)基金項(xiàng)目(2011021017)