基于能量有效和多跳的層次型拓?fù)淇刂扑惴?/h1>
2013-02-26 03:41:40譚軍等
價值工程 2013年3期 關(guān)鍵詞：仿真
譚軍 等
摘要： 拓?fù)淇刂剖菬o線傳感器網(wǎng)絡(luò)技術(shù)中的一個重要研究方向，良好的拓?fù)淇刂茩C(jī)制能夠提高路由協(xié)議和MAC協(xié)議的效率，為數(shù)據(jù)融合、時間同步和目標(biāo)定位等很多方面提供基礎(chǔ)。本文在提出一種基于能量有效和多跳的層次型拓?fù)淇刂扑惴?。算法在簇首選擇階段綜合考慮節(jié)點(diǎn)剩余能量、節(jié)點(diǎn)密度、節(jié)點(diǎn)間距離，在非簇首節(jié)點(diǎn)加入簇階段綜合考慮節(jié)點(diǎn)間剩余能量及距離，數(shù)據(jù)傳輸階段根據(jù)臨界條件來決定簇內(nèi)數(shù)據(jù)傳輸采用多跳或者單跳的數(shù)據(jù)傳輸?shù)臋C(jī)制。通過仿真軟件驗(yàn)證發(fā)現(xiàn)算法使得網(wǎng)絡(luò)分簇情況更加均衡，節(jié)點(diǎn)的平均功耗更少，更合理，網(wǎng)絡(luò)的生存時間更長。
Abstract： Topology control is an important research direction of wireless sensor network technology， the good topology control mechanism can improve the efficiency of the routing protocol and MAC protocol， and provide basis for data fusion， time synchronization， and target location. The paper puts forward a hierarchical topology control algorithm based on energy efficient and multihop. The Algorithm overall considers the node residual energy， node density， and distance between nodes in cluster head selection， and considers the node residual energy and distance between nodes when non-cluster head node joining cluster， and at the stage of data transmission， determines the transmission way according to the critical conditions. The algorithm is proved that it makes the network clumps situation more balanced， the average power consumption of node is less， more reasonable， and network life time is longer.
關(guān)鍵詞： 能量有效；多跳；無線傳感器網(wǎng)絡(luò)；拓?fù)淇刂?；仿?/p>
Key words： energy efficient；multihop；wireless sensor network （WSN）；topology control；simulation
中圖分類號：TP39 文獻(xiàn)標(biāo)識碼：A 文章編號：1006-4311（2013）03-0186-03
0 引言
無線傳感器網(wǎng)絡(luò)集成了傳感器技術(shù)、嵌入式系統(tǒng)技術(shù)、微機(jī)電系統(tǒng)技術(shù)、分布式信息處理技術(shù)以及無線通信技術(shù)，有著不可估量的應(yīng)用前景。無線傳感器網(wǎng)絡(luò)采用的傳感器體積小、能量少、節(jié)點(diǎn)部署環(huán)境較差[1]。對于能量受限的無線傳感器網(wǎng)絡(luò)來說，在確保網(wǎng)絡(luò)應(yīng)用的前提下節(jié)約能量消耗是一個關(guān)鍵問題。通過拓?fù)淇刂萍夹g(shù)生成優(yōu)化的拓?fù)浣Y(jié)構(gòu)可以實(shí)現(xiàn)節(jié)約能源消耗。
1 LEACH算法的特點(diǎn)
LEACH算法自適應(yīng)性好，容錯性高，并且能夠有效的延長網(wǎng)絡(luò)的壽命[2]。但是這種算法也存在著自身的缺點(diǎn)：
①簇首節(jié)點(diǎn)分布不合理。由于簇首產(chǎn)生的隨機(jī)性會導(dǎo)致整個網(wǎng)絡(luò)分簇不均勻，致使部分簇首相距基站遠(yuǎn)近不一，從加重某些簇首節(jié)點(diǎn)的負(fù)擔(dān)，降低網(wǎng)絡(luò)負(fù)載平衡度。
②簇內(nèi)節(jié)點(diǎn)分布不均勻。因?yàn)槭请S機(jī)性的產(chǎn)生簇首，所以就可能造成簇首負(fù)擔(dān)的節(jié)點(diǎn)不均衡，網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)分布不均勻使得簇首節(jié)點(diǎn)消耗能耗不一，造成網(wǎng)絡(luò)能量負(fù)載不平衡，減少了網(wǎng)絡(luò)生存時間。
③簇首選舉中沒有考慮節(jié)點(diǎn)的剩余能量，剩余能量少的節(jié)點(diǎn)一旦當(dāng)選為簇首，會導(dǎo)致該簇失效，甚至網(wǎng)絡(luò)癱瘓。
④簇內(nèi)節(jié)點(diǎn)Hj直接把數(shù)據(jù)傳輸給簇首節(jié)點(diǎn)CHi，當(dāng)兩者之間的距離較遠(yuǎn)時，會加重簇內(nèi)節(jié)點(diǎn)的能源消耗以及簇首節(jié)點(diǎn)的能源消耗。
2 系統(tǒng)模型
本文采用文獻(xiàn)[3]中的無線通信能量消耗模型，節(jié)點(diǎn)發(fā)送l bit的數(shù)據(jù)所消耗的能量為ETx（l，d），由發(fā)射電路損耗和功率放大損耗兩部分組成，即公式（1）所示：
ETx（l，d）=ETx-elec（l）+ETx-mp（l，d）=l×Eelec+l×ε×dβ （1）
Eelec表示發(fā)射電路和接收電路損耗的能量消耗，在該模型中兩者取相同值，能量消耗值與消息長度l成正比。功率放大時的能量消耗與發(fā)射節(jié)點(diǎn)和接收節(jié)點(diǎn)之間的傳輸距離d有關(guān)。根據(jù)傳輸距離d與給定閾值d0之間的關(guān)系，發(fā)送節(jié)點(diǎn)選擇不同的能量衰減模型計算發(fā)送數(shù)據(jù)所消耗的能量，即當(dāng)傳輸距離小于d0時，采用自由空間模型，發(fā)送數(shù)據(jù)的能量消耗與距離的平方成正比關(guān)系；否則采用多路徑衰減模型，與距離的四次方成正比關(guān)系，如公式（2）所示：
E■（l，d）=l·E■+ε■·l·d■，d＜d■l·E■+ε■·l·d■，d？叟d■（2）
其中ε■、ε■分別表示這兩種模型功率放大所消耗的能量，d■=4πhrht/λ，ht和hr分別表示發(fā)射裝置和接收裝置的天線長度，λ表示標(biāo)志信號波長。
接收裝置每接收l bit數(shù)據(jù)的能量消耗為：
ERx（l，d）=ERx-elec（l）=l·Eelec （3）
3 LEACH-EAM算法的實(shí)現(xiàn)
LEACH-EAM算法采用LEACH算法中輪次轉(zhuǎn)換的方法，把每輪循環(huán)分為簇的建立階段和穩(wěn)定的數(shù)據(jù)通信階段，如圖1所示。
3.1 簇的建立階段 簇的建立階段由簇首確定和簇的形成兩個階段組成。
3.1.1 簇首確定 在簇首選舉上，算法采用基于節(jié)點(diǎn)密度爭先的簇首選舉以及允許已經(jīng)充當(dāng)過簇首的節(jié)點(diǎn)繼續(xù)參加選舉的方法。同時，引入節(jié)點(diǎn)當(dāng)選簇首次數(shù)限制F（i）和能量限制Et（i）兩個指標(biāo)，避免節(jié)點(diǎn)頻繁當(dāng)選簇首或者剩余能量少節(jié)點(diǎn)當(dāng)選簇首，造成節(jié)點(diǎn)加快死忙的問題。
簇首選舉時節(jié)點(diǎn)生成介于0-1的隨機(jī)數(shù)a，用a與簇首選舉閥值T（Ni）進(jìn)行比較（T（Ni）由公式（4）定義），a比T（Ni）小就具備當(dāng)選簇首的先決條件。
T（Ni）=■×1-D■（Ni），Ni∈G （4）
在公式中：P是一個0-1間的實(shí)數(shù)，為網(wǎng)絡(luò)中每輪節(jié)點(diǎn)成為簇首占所有節(jié)點(diǎn)的比例；r是當(dāng)前輪數(shù)；G是在前r-1輪內(nèi)未死忙節(jié)點(diǎn)集合，D（Ni）是節(jié)點(diǎn)密集度參數(shù)（由公式（5）定義）。
D（Ni）=■ （5）
Nd（i）為節(jié)點(diǎn)i的存活鄰居節(jié)點(diǎn)數(shù)。
公式（5）由LEACH算法公式修改而來，它與LEACH算法不同的是：（1） LEACH算法中禁止當(dāng)選過簇首的節(jié)點(diǎn)再次參選，會從另一方面造成簇首節(jié)點(diǎn)分布在網(wǎng)絡(luò)邊緣，網(wǎng)絡(luò)分簇不均勻，所以本算法的簇首選舉閥值把限制當(dāng)選過簇首的限制條件去掉，允許節(jié)點(diǎn)多次單選簇首；（2）增加密度集參數(shù)，由1-D2（Ni）可以看出，隨著節(jié)點(diǎn)周圍存活的節(jié)點(diǎn)數(shù)越多，1-D2（Ni）的值也就越大，節(jié)點(diǎn)當(dāng)選簇首的概率也就會越高，節(jié)點(diǎn)周圍存活的節(jié)點(diǎn)數(shù)越少，節(jié)點(diǎn)當(dāng)選簇首的概率也就會越低。而且每個節(jié)點(diǎn)密度集也會隨著時間的變化而發(fā)生改變。
算法在簇首選舉的過程中還要衡量節(jié)點(diǎn)當(dāng)選簇首次數(shù)限制F（i）和能量限制Et（i）兩個指標(biāo)，定義以下變量C（i），ei，Eavr。C（i）是節(jié)點(diǎn)在生命期內(nèi)中當(dāng)選簇首節(jié)點(diǎn)的統(tǒng)計次數(shù)，由節(jié)點(diǎn)通過累加得到，ei為節(jié)點(diǎn)剩余能量，由節(jié)點(diǎn)自己能量消耗情況得出，Eavr為全網(wǎng)存活節(jié)點(diǎn)的平均剩余能量，由Sink節(jié)點(diǎn)返回得出。其中
F（i）=■ （6）
Et（i）=■ （7）
R■為系統(tǒng)設(shè)定的最大選舉輪數(shù)，參數(shù)P為系統(tǒng)設(shè)定的最優(yōu)簇首比例。節(jié)點(diǎn)只有在指標(biāo)F（i），Et（i）都比實(shí)數(shù)1小的時候才具備當(dāng)選簇首的前提條件。通過指標(biāo)F（i）可以保證節(jié)點(diǎn)當(dāng)選簇首的次數(shù)控制在一定的范圍內(nèi)，避免節(jié)點(diǎn)過早死忙。通過能量限制Et（i）保證當(dāng)選簇首的節(jié)點(diǎn)剩余能量必須比全網(wǎng)存活節(jié)點(diǎn)的剩余能量大，避免剩余能量較少的節(jié)點(diǎn)擔(dān)任簇首。
在簇首選舉的過程中從節(jié)點(diǎn)密度集、節(jié)點(diǎn)當(dāng)選簇首次數(shù)限制和能量限制等三個方面對LEACH算法進(jìn)行改進(jìn)，簇首的選舉不再是單個節(jié)點(diǎn)的事情，而是周圍節(jié)點(diǎn)的聯(lián)合考慮。簇首選舉流程圖如圖2所示。
3.1.2 簇的形成 一個節(jié)點(diǎn)成為候選簇首節(jié)點(diǎn)后，就向其鄰居R范圍內(nèi)廣播成為獲勝簇首的消息，該消息包括節(jié)點(diǎn)的ID，剩余能量ei和坐標(biāo)，等待節(jié)點(diǎn)的加入。非候選簇首節(jié)點(diǎn)收到簇首的廣播消息后，則計算與每個候選簇首之間能量距離綜合權(quán)值參數(shù)wji（wji由公式（8）給出），選擇wji值大的簇首加入，如果存在與多個候選簇首節(jié)點(diǎn)的wji值相等，則選擇距離短的簇首加入，并向該簇首發(fā)回確認(rèn)消息，確認(rèn)消息包含節(jié)點(diǎn)的ID，剩余能量ei和坐標(biāo)[4]。
w■=■/d（j，i） （8）
其中e■為非簇首節(jié)點(diǎn)的剩余能量，d（j，i）為非簇首節(jié)點(diǎn)Hj與簇首CHi之間的距離。
節(jié)點(diǎn)在簇首選舉時間內(nèi)如果沒有收到來自候選簇首的消息，則該節(jié)點(diǎn)宣布成為簇首，并向其鄰居R范圍內(nèi)廣播當(dāng)選簇首的消息，該消息包括節(jié)點(diǎn)的ID，剩余能量ei和自身的地理位置，等待節(jié)點(diǎn)的加入，只有與該節(jié)點(diǎn)相同的沒有收到獲勝簇首消息的節(jié)點(diǎn)才需要對這條消息響應(yīng)，通過前面的能量距離綜合權(quán)值參數(shù)wji方法選出剩余的簇首。
3.2 穩(wěn)定的數(shù)據(jù)通信階段 LEACH-EAM算法在穩(wěn)定的數(shù)據(jù)通信階段簇內(nèi)數(shù)據(jù)傳輸采用多跳和單跳結(jié)合的方法。LEACH-EAM需要根據(jù)當(dāng)前條件是否滿足臨界條件來決定簇內(nèi)節(jié)點(diǎn)進(jìn)行多跳或者多跳的數(shù)據(jù)傳輸。
3.2.1 臨界條件 臨界條件的確定參考文獻(xiàn)[5]得出，在文獻(xiàn)中通過參數(shù)Q■（公式（9））確定臨界條件。
Q■=■ （9）
Q■為每個簇平均所占的面積。簇所覆蓋面積大小決定了該分簇是采用多跳或者單跳的傳輸方式。當(dāng)簇所占的面積滿足大于Q■時，采用多跳的傳輸方式，反之則采用單跳。
3.2.2 多跳的實(shí)現(xiàn)方法 在實(shí)現(xiàn)多跳的數(shù)據(jù)傳輸過程中，簇首CHi先根據(jù)簇內(nèi)成員節(jié)點(diǎn)的位置信息，采用最短路徑算法Dijkstra計算連接邊的權(quán)重意義上的最短路徑得到CHi出發(fā)到所有簇內(nèi)節(jié)點(diǎn)的路由路徑樹。根據(jù)公式（2）可計算連接邊的權(quán)重Eelec+εfriss-ampd2，因?yàn)榇亟Y(jié)構(gòu)中傳輸距離較短的特性，所以衰減因子選擇2。當(dāng)最短路徑計算完畢后，簇首CHi將路徑樹打包成消息廣播給簇內(nèi)節(jié)點(diǎn)[5]。簇內(nèi)節(jié)點(diǎn)Hj接收到路徑消息后，可從消息中得出自己的上一跳集合和下一跳集合。
4 算法仿真
4.1 仿真系統(tǒng)配置 仿真系統(tǒng)配置如下：傳感器網(wǎng)絡(luò)布置區(qū)域?yàn)?00m×100m，隨機(jī)分布的節(jié)點(diǎn)數(shù)為100個，基站位置固定在坐標(biāo)（50，50）處，節(jié)點(diǎn)的傳輸距離為10m—50m，節(jié)點(diǎn)初始能量為2J，節(jié)點(diǎn)接收和發(fā)送電路消耗的能量Eelec為50Nj/bit，信號放大器的放大倍數(shù)為0.0013pJ/bit/m4，增量Δ為2，EDA為0.009J/bit/signal，節(jié)點(diǎn)充當(dāng)簇首時間為100s[6]。
4.2 性能分析 為了評價算法對網(wǎng)絡(luò)性能的影響，為了更好地衡量網(wǎng)絡(luò)壽命、能量利用率和簇規(guī)模等幾個指標(biāo)，本仿真實(shí)驗(yàn)中測定了四個指標(biāo)，分別為：簇規(guī)模、網(wǎng)絡(luò)壽命、簇內(nèi)節(jié)點(diǎn)分布、平均功耗。
4.2.1 簇規(guī)模 簇規(guī)模指標(biāo)用來評價各簇節(jié)點(diǎn)數(shù)的平衡度。為比較LEACH-EAM算法在平衡各簇規(guī)模的作用，隨機(jī)抽取了算法在運(yùn)行過程中的分簇，如圖3所示?？梢钥闯鯨EACH-EAM結(jié)合節(jié)點(diǎn)剩余能量和節(jié)點(diǎn)密度選擇簇首，相比LEACH算法和DBPC算法簇首節(jié)點(diǎn)分布比較均勻，而且都分別位于各簇的中央地帶，較好地避免了簇首節(jié)點(diǎn)聚集或處于網(wǎng)絡(luò)邊緣的問題。
4.2.2 不同簇首比例網(wǎng)絡(luò)壽命 圖4為簇首比例P分別取0.04、0.05、0.1時，四種算法對網(wǎng)絡(luò)壽命的影響?？梢钥闯鲈?種不同簇首比例P下，因?yàn)長EACH—EAM算法在簇首選舉階段引入能量限制指標(biāo)，避免剩余能量少節(jié)點(diǎn)當(dāng)選簇首，在簇的形成階段，非簇首節(jié)點(diǎn)計算與每個候選簇首之間能量、距離綜合權(quán)值，并加入選擇綜合權(quán)值大的簇，簇內(nèi)節(jié)點(diǎn)采用多跳與單跳相結(jié)合的方式進(jìn)行數(shù)據(jù)傳輸，所以網(wǎng)絡(luò)壽命最長，OBCP次之，LEACH的網(wǎng)絡(luò)壽命最短。而且當(dāng)P=0.04時，LEACH-EAM的網(wǎng)絡(luò)存活時間最長。
4.2.3 簇內(nèi)節(jié)點(diǎn)分布 簇內(nèi)節(jié)點(diǎn)分布性能指標(biāo)反映網(wǎng)絡(luò)分簇情況是否均衡。如圖5所示，可以看出LEACH-EAM各簇包含的節(jié)點(diǎn)數(shù)相對于LEACH、DBCP更加集中，從而進(jìn)一步證明通過結(jié)合節(jié)點(diǎn)密度選舉簇首可以更有效平衡各個簇的規(guī)模。
4.2.4 不同網(wǎng)絡(luò)直徑下的網(wǎng)絡(luò)壽命、節(jié)點(diǎn)平均功耗 圖6和圖7分別表示在不同網(wǎng)絡(luò)直徑下的網(wǎng)絡(luò)壽命和節(jié)點(diǎn)平均功耗的對比情況。從圖中可以看出，隨著網(wǎng)絡(luò)直徑的增加，簇內(nèi)通信距離增大，造成簇內(nèi)消耗的能量也增大， LEACH-EAM相對LEACH算法、DBCP算法節(jié)點(diǎn)平均功耗是最少，網(wǎng)絡(luò)壽命最長。
5 結(jié)束語
本文LEACH算法進(jìn)行深入研究，提出了LEACH-EMA算法。通過簇首的確定、簇的形成兩個階段，簇內(nèi)數(shù)據(jù)傳輸方式實(shí)現(xiàn)了改進(jìn)算法，具備網(wǎng)絡(luò)分簇情況均衡，節(jié)點(diǎn)的平均功耗少；網(wǎng)絡(luò)的生存時間長的特點(diǎn)。
參考文獻(xiàn)：
[1]孫利民，李建中，陳渝等.無線傳感器[C].網(wǎng)絡(luò)清華大學(xué)出版社，2005．5，89．107.
[2]喬俊峰，劉三陽，曹祥宇.無線傳感器網(wǎng)絡(luò)中基于節(jié)點(diǎn)密度的簇算法[J].計算機(jī)科學(xué)，2009，36（12）：46-49.
[3]Heinzelman W， Chandrakasan A， Balakrishnan H. Energy-efficient communication protocol for wireless micro-sensor networks[C]. Proceedings of t he 33rd Annual Hawaii International Conference on System Sciences， Maui， 2007.3005-30l4.
[4]郝曉辰，翟明，劉彬，張增仁.負(fù)載均衡的無線傳感器網(wǎng)絡(luò)拓?fù)淇刂扑惴╗J].計算機(jī)工程，2009，35（05）：84-86.
[5]湯強(qiáng).無線傳感器網(wǎng)絡(luò)層次拓?fù)淇刂扑惴ㄑ芯?華中科技大學(xué)博士學(xué)位論文.2010.6.1.
[6]Younis O， Fahmy S. Heed： A Hybrid， Energy-efficient， Distributed Clustering Approach for Ad Hoc Sensor Networks[J]. IEEE Transactions on Mobile Computing， 2004，3（4）： 660-669.
猜你喜歡
Proteus仿真軟件在單片機(jī)原理及應(yīng)用課程教學(xué)中的應(yīng)用中國教育技術(shù)裝備(2016年20期)2016-12-12 10:09:15 工業(yè)機(jī)器人模擬仿真技術(shù)在職業(yè)教育中的應(yīng)用淺析中小企業(yè)管理與科技·下旬刊(2016年10期)2016-11-18 20:57:34 一種幫助幼兒車內(nèi)脫險應(yīng)急裝置的仿真分析科技資訊(2016年18期)2016-11-15 20:09:22 論虛擬仿真實(shí)訓(xùn)系統(tǒng)在口腔實(shí)驗(yàn)教學(xué)中的應(yīng)用科技資訊(2016年18期)2016-11-15 07:55:28 基于機(jī)電設(shè)備電氣控制線路排故的仿真系統(tǒng)設(shè)計價值工程(2016年29期)2016-11-14 02:01:16 航空電氣系統(tǒng)中故障電弧研究電子技術(shù)與軟件工程(2016年18期)2016-11-14 00:46:54 Buck開關(guān)變換器的基本參數(shù)設(shè)計及仿真分析數(shù)字技術(shù)與應(yīng)用(2016年9期)2016-11-09 23:25:33 試析PLC控制下的自動化立體倉庫仿真情況分析數(shù)字技術(shù)與應(yīng)用(2016年9期)2016-11-09 22:09:07 基于MADYMO的航空座椅約束系統(tǒng)優(yōu)化設(shè)計科技視界(2016年18期)2016-11-03 21:44:44 中國體態(tài)假人模型與FAA Hybrid Ⅲ 型假人模型沖擊差異性分析科技視界(2016年18期)2016-11-03 20:31:49
譚軍 等
摘要： 拓?fù)淇刂剖菬o線傳感器網(wǎng)絡(luò)技術(shù)中的一個重要研究方向，良好的拓?fù)淇刂茩C(jī)制能夠提高路由協(xié)議和MAC協(xié)議的效率，為數(shù)據(jù)融合、時間同步和目標(biāo)定位等很多方面提供基礎(chǔ)。本文在提出一種基于能量有效和多跳的層次型拓?fù)淇刂扑惴?。算法在簇首選擇階段綜合考慮節(jié)點(diǎn)剩余能量、節(jié)點(diǎn)密度、節(jié)點(diǎn)間距離，在非簇首節(jié)點(diǎn)加入簇階段綜合考慮節(jié)點(diǎn)間剩余能量及距離，數(shù)據(jù)傳輸階段根據(jù)臨界條件來決定簇內(nèi)數(shù)據(jù)傳輸采用多跳或者單跳的數(shù)據(jù)傳輸?shù)臋C(jī)制。通過仿真軟件驗(yàn)證發(fā)現(xiàn)算法使得網(wǎng)絡(luò)分簇情況更加均衡，節(jié)點(diǎn)的平均功耗更少，更合理，網(wǎng)絡(luò)的生存時間更長。
Abstract： Topology control is an important research direction of wireless sensor network technology， the good topology control mechanism can improve the efficiency of the routing protocol and MAC protocol， and provide basis for data fusion， time synchronization， and target location. The paper puts forward a hierarchical topology control algorithm based on energy efficient and multihop. The Algorithm overall considers the node residual energy， node density， and distance between nodes in cluster head selection， and considers the node residual energy and distance between nodes when non-cluster head node joining cluster， and at the stage of data transmission， determines the transmission way according to the critical conditions. The algorithm is proved that it makes the network clumps situation more balanced， the average power consumption of node is less， more reasonable， and network life time is longer.
關(guān)鍵詞： 能量有效；多跳；無線傳感器網(wǎng)絡(luò)；拓?fù)淇刂?；仿?/p>
Key words： energy efficient；multihop；wireless sensor network （WSN）；topology control；simulation
中圖分類號：TP39 文獻(xiàn)標(biāo)識碼：A 文章編號：1006-4311（2013）03-0186-03
0 引言
無線傳感器網(wǎng)絡(luò)集成了傳感器技術(shù)、嵌入式系統(tǒng)技術(shù)、微機(jī)電系統(tǒng)技術(shù)、分布式信息處理技術(shù)以及無線通信技術(shù)，有著不可估量的應(yīng)用前景。無線傳感器網(wǎng)絡(luò)采用的傳感器體積小、能量少、節(jié)點(diǎn)部署環(huán)境較差[1]。對于能量受限的無線傳感器網(wǎng)絡(luò)來說，在確保網(wǎng)絡(luò)應(yīng)用的前提下節(jié)約能量消耗是一個關(guān)鍵問題。通過拓?fù)淇刂萍夹g(shù)生成優(yōu)化的拓?fù)浣Y(jié)構(gòu)可以實(shí)現(xiàn)節(jié)約能源消耗。
1 LEACH算法的特點(diǎn)
LEACH算法自適應(yīng)性好，容錯性高，并且能夠有效的延長網(wǎng)絡(luò)的壽命[2]。但是這種算法也存在著自身的缺點(diǎn)：
①簇首節(jié)點(diǎn)分布不合理。由于簇首產(chǎn)生的隨機(jī)性會導(dǎo)致整個網(wǎng)絡(luò)分簇不均勻，致使部分簇首相距基站遠(yuǎn)近不一，從加重某些簇首節(jié)點(diǎn)的負(fù)擔(dān)，降低網(wǎng)絡(luò)負(fù)載平衡度。
②簇內(nèi)節(jié)點(diǎn)分布不均勻。因?yàn)槭请S機(jī)性的產(chǎn)生簇首，所以就可能造成簇首負(fù)擔(dān)的節(jié)點(diǎn)不均衡，網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)分布不均勻使得簇首節(jié)點(diǎn)消耗能耗不一，造成網(wǎng)絡(luò)能量負(fù)載不平衡，減少了網(wǎng)絡(luò)生存時間。
③簇首選舉中沒有考慮節(jié)點(diǎn)的剩余能量，剩余能量少的節(jié)點(diǎn)一旦當(dāng)選為簇首，會導(dǎo)致該簇失效，甚至網(wǎng)絡(luò)癱瘓。
④簇內(nèi)節(jié)點(diǎn)Hj直接把數(shù)據(jù)傳輸給簇首節(jié)點(diǎn)CHi，當(dāng)兩者之間的距離較遠(yuǎn)時，會加重簇內(nèi)節(jié)點(diǎn)的能源消耗以及簇首節(jié)點(diǎn)的能源消耗。
2 系統(tǒng)模型
本文采用文獻(xiàn)[3]中的無線通信能量消耗模型，節(jié)點(diǎn)發(fā)送l bit的數(shù)據(jù)所消耗的能量為ETx（l，d），由發(fā)射電路損耗和功率放大損耗兩部分組成，即公式（1）所示：
ETx（l，d）=ETx-elec（l）+ETx-mp（l，d）=l×Eelec+l×ε×dβ （1）
Eelec表示發(fā)射電路和接收電路損耗的能量消耗，在該模型中兩者取相同值，能量消耗值與消息長度l成正比。功率放大時的能量消耗與發(fā)射節(jié)點(diǎn)和接收節(jié)點(diǎn)之間的傳輸距離d有關(guān)。根據(jù)傳輸距離d與給定閾值d0之間的關(guān)系，發(fā)送節(jié)點(diǎn)選擇不同的能量衰減模型計算發(fā)送數(shù)據(jù)所消耗的能量，即當(dāng)傳輸距離小于d0時，采用自由空間模型，發(fā)送數(shù)據(jù)的能量消耗與距離的平方成正比關(guān)系；否則采用多路徑衰減模型，與距離的四次方成正比關(guān)系，如公式（2）所示：
E■（l，d）=l·E■+ε■·l·d■，d＜d■l·E■+ε■·l·d■，d？叟d■（2）
其中ε■、ε■分別表示這兩種模型功率放大所消耗的能量，d■=4πhrht/λ，ht和hr分別表示發(fā)射裝置和接收裝置的天線長度，λ表示標(biāo)志信號波長。
接收裝置每接收l bit數(shù)據(jù)的能量消耗為：
ERx（l，d）=ERx-elec（l）=l·Eelec （3）
3 LEACH-EAM算法的實(shí)現(xiàn)
LEACH-EAM算法采用LEACH算法中輪次轉(zhuǎn)換的方法，把每輪循環(huán)分為簇的建立階段和穩(wěn)定的數(shù)據(jù)通信階段，如圖1所示。
3.1 簇的建立階段 簇的建立階段由簇首確定和簇的形成兩個階段組成。
3.1.1 簇首確定 在簇首選舉上，算法采用基于節(jié)點(diǎn)密度爭先的簇首選舉以及允許已經(jīng)充當(dāng)過簇首的節(jié)點(diǎn)繼續(xù)參加選舉的方法。同時，引入節(jié)點(diǎn)當(dāng)選簇首次數(shù)限制F（i）和能量限制Et（i）兩個指標(biāo)，避免節(jié)點(diǎn)頻繁當(dāng)選簇首或者剩余能量少節(jié)點(diǎn)當(dāng)選簇首，造成節(jié)點(diǎn)加快死忙的問題。
簇首選舉時節(jié)點(diǎn)生成介于0-1的隨機(jī)數(shù)a，用a與簇首選舉閥值T（Ni）進(jìn)行比較（T（Ni）由公式（4）定義），a比T（Ni）小就具備當(dāng)選簇首的先決條件。
T（Ni）=■×1-D■（Ni），Ni∈G （4）
在公式中：P是一個0-1間的實(shí)數(shù)，為網(wǎng)絡(luò)中每輪節(jié)點(diǎn)成為簇首占所有節(jié)點(diǎn)的比例；r是當(dāng)前輪數(shù)；G是在前r-1輪內(nèi)未死忙節(jié)點(diǎn)集合，D（Ni）是節(jié)點(diǎn)密集度參數(shù)（由公式（5）定義）。
D（Ni）=■ （5）
Nd（i）為節(jié)點(diǎn)i的存活鄰居節(jié)點(diǎn)數(shù)。
公式（5）由LEACH算法公式修改而來，它與LEACH算法不同的是：（1） LEACH算法中禁止當(dāng)選過簇首的節(jié)點(diǎn)再次參選，會從另一方面造成簇首節(jié)點(diǎn)分布在網(wǎng)絡(luò)邊緣，網(wǎng)絡(luò)分簇不均勻，所以本算法的簇首選舉閥值把限制當(dāng)選過簇首的限制條件去掉，允許節(jié)點(diǎn)多次單選簇首；（2）增加密度集參數(shù)，由1-D2（Ni）可以看出，隨著節(jié)點(diǎn)周圍存活的節(jié)點(diǎn)數(shù)越多，1-D2（Ni）的值也就越大，節(jié)點(diǎn)當(dāng)選簇首的概率也就會越高，節(jié)點(diǎn)周圍存活的節(jié)點(diǎn)數(shù)越少，節(jié)點(diǎn)當(dāng)選簇首的概率也就會越低。而且每個節(jié)點(diǎn)密度集也會隨著時間的變化而發(fā)生改變。
算法在簇首選舉的過程中還要衡量節(jié)點(diǎn)當(dāng)選簇首次數(shù)限制F（i）和能量限制Et（i）兩個指標(biāo)，定義以下變量C（i），ei，Eavr。C（i）是節(jié)點(diǎn)在生命期內(nèi)中當(dāng)選簇首節(jié)點(diǎn)的統(tǒng)計次數(shù)，由節(jié)點(diǎn)通過累加得到，ei為節(jié)點(diǎn)剩余能量，由節(jié)點(diǎn)自己能量消耗情況得出，Eavr為全網(wǎng)存活節(jié)點(diǎn)的平均剩余能量，由Sink節(jié)點(diǎn)返回得出。其中
F（i）=■ （6）
Et（i）=■ （7）
R■為系統(tǒng)設(shè)定的最大選舉輪數(shù)，參數(shù)P為系統(tǒng)設(shè)定的最優(yōu)簇首比例。節(jié)點(diǎn)只有在指標(biāo)F（i），Et（i）都比實(shí)數(shù)1小的時候才具備當(dāng)選簇首的前提條件。通過指標(biāo)F（i）可以保證節(jié)點(diǎn)當(dāng)選簇首的次數(shù)控制在一定的范圍內(nèi)，避免節(jié)點(diǎn)過早死忙。通過能量限制Et（i）保證當(dāng)選簇首的節(jié)點(diǎn)剩余能量必須比全網(wǎng)存活節(jié)點(diǎn)的剩余能量大，避免剩余能量較少的節(jié)點(diǎn)擔(dān)任簇首。
在簇首選舉的過程中從節(jié)點(diǎn)密度集、節(jié)點(diǎn)當(dāng)選簇首次數(shù)限制和能量限制等三個方面對LEACH算法進(jìn)行改進(jìn)，簇首的選舉不再是單個節(jié)點(diǎn)的事情，而是周圍節(jié)點(diǎn)的聯(lián)合考慮。簇首選舉流程圖如圖2所示。
3.1.2 簇的形成 一個節(jié)點(diǎn)成為候選簇首節(jié)點(diǎn)后，就向其鄰居R范圍內(nèi)廣播成為獲勝簇首的消息，該消息包括節(jié)點(diǎn)的ID，剩余能量ei和坐標(biāo)，等待節(jié)點(diǎn)的加入。非候選簇首節(jié)點(diǎn)收到簇首的廣播消息后，則計算與每個候選簇首之間能量距離綜合權(quán)值參數(shù)wji（wji由公式（8）給出），選擇wji值大的簇首加入，如果存在與多個候選簇首節(jié)點(diǎn)的wji值相等，則選擇距離短的簇首加入，并向該簇首發(fā)回確認(rèn)消息，確認(rèn)消息包含節(jié)點(diǎn)的ID，剩余能量ei和坐標(biāo)[4]。
w■=■/d（j，i） （8）
其中e■為非簇首節(jié)點(diǎn)的剩余能量，d（j，i）為非簇首節(jié)點(diǎn)Hj與簇首CHi之間的距離。
節(jié)點(diǎn)在簇首選舉時間內(nèi)如果沒有收到來自候選簇首的消息，則該節(jié)點(diǎn)宣布成為簇首，并向其鄰居R范圍內(nèi)廣播當(dāng)選簇首的消息，該消息包括節(jié)點(diǎn)的ID，剩余能量ei和自身的地理位置，等待節(jié)點(diǎn)的加入，只有與該節(jié)點(diǎn)相同的沒有收到獲勝簇首消息的節(jié)點(diǎn)才需要對這條消息響應(yīng)，通過前面的能量距離綜合權(quán)值參數(shù)wji方法選出剩余的簇首。
3.2 穩(wěn)定的數(shù)據(jù)通信階段 LEACH-EAM算法在穩(wěn)定的數(shù)據(jù)通信階段簇內(nèi)數(shù)據(jù)傳輸采用多跳和單跳結(jié)合的方法。LEACH-EAM需要根據(jù)當(dāng)前條件是否滿足臨界條件來決定簇內(nèi)節(jié)點(diǎn)進(jìn)行多跳或者多跳的數(shù)據(jù)傳輸。
3.2.1 臨界條件 臨界條件的確定參考文獻(xiàn)[5]得出，在文獻(xiàn)中通過參數(shù)Q■（公式（9））確定臨界條件。
Q■=■ （9）
Q■為每個簇平均所占的面積。簇所覆蓋面積大小決定了該分簇是采用多跳或者單跳的傳輸方式。當(dāng)簇所占的面積滿足大于Q■時，采用多跳的傳輸方式，反之則采用單跳。
3.2.2 多跳的實(shí)現(xiàn)方法 在實(shí)現(xiàn)多跳的數(shù)據(jù)傳輸過程中，簇首CHi先根據(jù)簇內(nèi)成員節(jié)點(diǎn)的位置信息，采用最短路徑算法Dijkstra計算連接邊的權(quán)重意義上的最短路徑得到CHi出發(fā)到所有簇內(nèi)節(jié)點(diǎn)的路由路徑樹。根據(jù)公式（2）可計算連接邊的權(quán)重Eelec+εfriss-ampd2，因?yàn)榇亟Y(jié)構(gòu)中傳輸距離較短的特性，所以衰減因子選擇2。當(dāng)最短路徑計算完畢后，簇首CHi將路徑樹打包成消息廣播給簇內(nèi)節(jié)點(diǎn)[5]。簇內(nèi)節(jié)點(diǎn)Hj接收到路徑消息后，可從消息中得出自己的上一跳集合和下一跳集合。
4 算法仿真
4.1 仿真系統(tǒng)配置 仿真系統(tǒng)配置如下：傳感器網(wǎng)絡(luò)布置區(qū)域?yàn)?00m×100m，隨機(jī)分布的節(jié)點(diǎn)數(shù)為100個，基站位置固定在坐標(biāo)（50，50）處，節(jié)點(diǎn)的傳輸距離為10m—50m，節(jié)點(diǎn)初始能量為2J，節(jié)點(diǎn)接收和發(fā)送電路消耗的能量Eelec為50Nj/bit，信號放大器的放大倍數(shù)為0.0013pJ/bit/m4，增量Δ為2，EDA為0.009J/bit/signal，節(jié)點(diǎn)充當(dāng)簇首時間為100s[6]。
4.2 性能分析 為了評價算法對網(wǎng)絡(luò)性能的影響，為了更好地衡量網(wǎng)絡(luò)壽命、能量利用率和簇規(guī)模等幾個指標(biāo)，本仿真實(shí)驗(yàn)中測定了四個指標(biāo)，分別為：簇規(guī)模、網(wǎng)絡(luò)壽命、簇內(nèi)節(jié)點(diǎn)分布、平均功耗。
4.2.1 簇規(guī)模 簇規(guī)模指標(biāo)用來評價各簇節(jié)點(diǎn)數(shù)的平衡度。為比較LEACH-EAM算法在平衡各簇規(guī)模的作用，隨機(jī)抽取了算法在運(yùn)行過程中的分簇，如圖3所示?？梢钥闯鯨EACH-EAM結(jié)合節(jié)點(diǎn)剩余能量和節(jié)點(diǎn)密度選擇簇首，相比LEACH算法和DBPC算法簇首節(jié)點(diǎn)分布比較均勻，而且都分別位于各簇的中央地帶，較好地避免了簇首節(jié)點(diǎn)聚集或處于網(wǎng)絡(luò)邊緣的問題。
4.2.2 不同簇首比例網(wǎng)絡(luò)壽命 圖4為簇首比例P分別取0.04、0.05、0.1時，四種算法對網(wǎng)絡(luò)壽命的影響?？梢钥闯鲈?種不同簇首比例P下，因?yàn)長EACH—EAM算法在簇首選舉階段引入能量限制指標(biāo)，避免剩余能量少節(jié)點(diǎn)當(dāng)選簇首，在簇的形成階段，非簇首節(jié)點(diǎn)計算與每個候選簇首之間能量、距離綜合權(quán)值，并加入選擇綜合權(quán)值大的簇，簇內(nèi)節(jié)點(diǎn)采用多跳與單跳相結(jié)合的方式進(jìn)行數(shù)據(jù)傳輸，所以網(wǎng)絡(luò)壽命最長，OBCP次之，LEACH的網(wǎng)絡(luò)壽命最短。而且當(dāng)P=0.04時，LEACH-EAM的網(wǎng)絡(luò)存活時間最長。
4.2.3 簇內(nèi)節(jié)點(diǎn)分布 簇內(nèi)節(jié)點(diǎn)分布性能指標(biāo)反映網(wǎng)絡(luò)分簇情況是否均衡。如圖5所示，可以看出LEACH-EAM各簇包含的節(jié)點(diǎn)數(shù)相對于LEACH、DBCP更加集中，從而進(jìn)一步證明通過結(jié)合節(jié)點(diǎn)密度選舉簇首可以更有效平衡各個簇的規(guī)模。
4.2.4 不同網(wǎng)絡(luò)直徑下的網(wǎng)絡(luò)壽命、節(jié)點(diǎn)平均功耗 圖6和圖7分別表示在不同網(wǎng)絡(luò)直徑下的網(wǎng)絡(luò)壽命和節(jié)點(diǎn)平均功耗的對比情況。從圖中可以看出，隨著網(wǎng)絡(luò)直徑的增加，簇內(nèi)通信距離增大，造成簇內(nèi)消耗的能量也增大， LEACH-EAM相對LEACH算法、DBCP算法節(jié)點(diǎn)平均功耗是最少，網(wǎng)絡(luò)壽命最長。
5 結(jié)束語
本文LEACH算法進(jìn)行深入研究，提出了LEACH-EMA算法。通過簇首的確定、簇的形成兩個階段，簇內(nèi)數(shù)據(jù)傳輸方式實(shí)現(xiàn)了改進(jìn)算法，具備網(wǎng)絡(luò)分簇情況均衡，節(jié)點(diǎn)的平均功耗少；網(wǎng)絡(luò)的生存時間長的特點(diǎn)。
參考文獻(xiàn)：
[1]孫利民，李建中，陳渝等.無線傳感器[C].網(wǎng)絡(luò)清華大學(xué)出版社，2005．5，89．107.
[2]喬俊峰，劉三陽，曹祥宇.無線傳感器網(wǎng)絡(luò)中基于節(jié)點(diǎn)密度的簇算法[J].計算機(jī)科學(xué)，2009，36（12）：46-49.
[3]Heinzelman W， Chandrakasan A， Balakrishnan H. Energy-efficient communication protocol for wireless micro-sensor networks[C]. Proceedings of t he 33rd Annual Hawaii International Conference on System Sciences， Maui， 2007.3005-30l4.
[4]郝曉辰，翟明，劉彬，張增仁.負(fù)載均衡的無線傳感器網(wǎng)絡(luò)拓?fù)淇刂扑惴╗J].計算機(jī)工程，2009，35（05）：84-86.
[5]湯強(qiáng).無線傳感器網(wǎng)絡(luò)層次拓?fù)淇刂扑惴ㄑ芯?華中科技大學(xué)博士學(xué)位論文.2010.6.1.
[6]Younis O， Fahmy S. Heed： A Hybrid， Energy-efficient， Distributed Clustering Approach for Ad Hoc Sensor Networks[J]. IEEE Transactions on Mobile Computing， 2004，3（4）： 660-669.
猜你喜歡
中國教育技術(shù)裝備(2016年20期)2016-12-12 10:09:15
中小企業(yè)管理與科技·下旬刊(2016年10期)2016-11-18 20:57:34
科技資訊(2016年18期)2016-11-15 20:09:22
科技資訊(2016年18期)2016-11-15 07:55:28
價值工程(2016年29期)2016-11-14 02:01:16
電子技術(shù)與軟件工程(2016年18期)2016-11-14 00:46:54
數(shù)字技術(shù)與應(yīng)用(2016年9期)2016-11-09 23:25:33
數(shù)字技術(shù)與應(yīng)用(2016年9期)2016-11-09 22:09:07
科技視界(2016年18期)2016-11-03 21:44:44
科技視界(2016年18期)2016-11-03 20:31:49
