基于改進(jìn)蟻群算法的高能效WSN協(xié)作傳輸策略

李燕龍，王俊義，符杰林，仇洪冰

(桂林電子科技大學(xué) 信息與通信學(xué)院，廣西 桂林 541004)

基于改進(jìn)蟻群算法的高能效WSN協(xié)作傳輸策略

李燕龍，王俊義，符杰林，仇洪冰

(桂林電子科技大學(xué) 信息與通信學(xué)院，廣西 桂林 541004)

針對傳統(tǒng)傳感器網(wǎng)絡(luò)分簇不均勻，數(shù)據(jù)傳輸能耗相對較高的問題，提出了I-CoopACO (Cooperative transmission scheme based improved Ant Colony Optimal algorithm)算法。該算法在協(xié)作LEACH(Low Energy Adaptive Clustering Hierarchy)的技術(shù)基礎(chǔ)上，改進(jìn)了成簇過程，使得分簇規(guī)模更加均勻；在穩(wěn)定傳輸階段，利用節(jié)點(diǎn)剩余能量和傳輸功耗構(gòu)建啟發(fā)因子，通過改進(jìn)的蟻群算法搜索下一跳中繼節(jié)點(diǎn)獲得最優(yōu)節(jié)點(diǎn)，使得傳輸功耗更低，能耗更均衡。仿真結(jié)果表明，在隨機(jī)分布的感知網(wǎng)絡(luò)中，I-CoopACO算法減少了傳輸能耗，均衡了網(wǎng)絡(luò)負(fù)載，延長了網(wǎng)絡(luò)工作壽命，比協(xié)作LEACH算法延長了64.93%的工作壽命。

無線傳感器網(wǎng)絡(luò)；能效優(yōu)化；傳輸路由；虛擬MIMO；蟻群算法

傳統(tǒng)無線傳感器網(wǎng)絡(luò)通過各類由電池供電的微型傳感器協(xié)作地實(shí)時(shí)監(jiān)測、感知和采集各種環(huán)境或監(jiān)測對象的信息[1]，信息數(shù)據(jù)通過以無線多跳的傳輸方式傳送到用戶端。一旦布置到感知區(qū)域中，電池很難被替換，每一個(gè)節(jié)點(diǎn)傳輸?shù)男畔⒈忍厥怯邢薜?，因此，減少能量消耗就成為傳感器網(wǎng)絡(luò)的一個(gè)重要研究問題。在能量不可補(bǔ)充的傳感器網(wǎng)絡(luò)中，主要通過沖突避免、減少開銷、增加休眠時(shí)間以及優(yōu)化路由[2]等方法減少能量消耗，而優(yōu)化路由是其中一個(gè)非常重要的方面。高能效的路由算法主要有單跳、多跳、協(xié)作MIMO單跳、多跳[3-4]，大多數(shù)是通過分簇收集數(shù)據(jù)，數(shù)據(jù)匯聚后通過不同傳輸方式發(fā)送給遠(yuǎn)方的基站。

目前，大多數(shù)路由算法例如LEACH[5]算法，為了降低能耗采取隨機(jī)輪詢選擇簇頭，分簇收集數(shù)據(jù)。但是隨機(jī)選擇的簇頭，不能保證經(jīng)過數(shù)據(jù)匯聚融合后傳輸給匯聚節(jié)點(diǎn)的過程能耗最低，也不能保證分布均勻，這樣形成的網(wǎng)絡(luò)拓?fù)洳荒苓_(dá)到最優(yōu)分布，選擇簇頭時(shí)大多也沒有考慮到節(jié)點(diǎn)的剩余能量。針對這些問題，本文優(yōu)化了成簇算法，在每一輪成簇過程中，改進(jìn)了簇頭選擇方式，調(diào)整了成簇規(guī)模，從而數(shù)據(jù)匯聚傳輸過程中能耗更低，網(wǎng)絡(luò)能耗更加均勻。

在成簇之后，傳統(tǒng)的傳輸方法最早采用單跳、多跳傳輸，這樣的傳輸在距離較遠(yuǎn)時(shí)需要較高的發(fā)射功率，而多跳傳輸時(shí)，選擇的中繼節(jié)點(diǎn)往往不是傳輸能耗最低的，或者剩余能量最多的。在感知區(qū)域中，一般情況下節(jié)點(diǎn)密度較高，簇內(nèi)很容易選擇出協(xié)作節(jié)點(diǎn)構(gòu)成虛擬MIMO(Multiple Input Multiple Output)系統(tǒng)[6]。在同等誤碼率要求下，協(xié)作MIMO技術(shù)利用空間復(fù)用和分集降低了發(fā)射功率，節(jié)省能耗。因此，本文在自適應(yīng)分簇之后，使用協(xié)作MIMO技術(shù)傳輸數(shù)據(jù)，根據(jù)蟻群智能算法搜索中繼節(jié)點(diǎn)，重新構(gòu)建啟發(fā)因子，優(yōu)化路由，降低中繼節(jié)點(diǎn)數(shù)據(jù)傳輸功耗，均衡負(fù)載，延長網(wǎng)絡(luò)工作壽命。

1 傳感器網(wǎng)絡(luò)系統(tǒng)及能耗模型

無線傳感器網(wǎng)絡(luò)是具有大量感知節(jié)點(diǎn)隨機(jī)均勻分布的網(wǎng)絡(luò)，經(jīng)過信息采集、融合、傳輸給基站。在本文中，假設(shè)一個(gè)具有如圖1所示的網(wǎng)絡(luò)模型，網(wǎng)絡(luò)中感知節(jié)點(diǎn)都是傳統(tǒng)節(jié)點(diǎn)，能量受限，節(jié)點(diǎn)一旦布置后，固定不能移動(dòng)，且遠(yuǎn)離匯聚節(jié)點(diǎn)，節(jié)點(diǎn)可以自適應(yīng)地改變發(fā)射功率和傳輸速率，全網(wǎng)時(shí)間同步，匯聚節(jié)點(diǎn)能量供應(yīng)充足。

圖1 協(xié)作多跳傳輸系統(tǒng)模型

在無線傳感器網(wǎng)路中，為了簡化分析，能量消耗可以分成兩部分[7]，如式(1)所示，數(shù)據(jù)本地傳輸和遠(yuǎn)程傳輸消耗，每一部分能耗又分為兩部分，數(shù)據(jù)傳輸能耗和電路能耗。在無線傳感器網(wǎng)絡(luò)能耗模型中，能量消耗公式采用一階無線電模式，其中，簇內(nèi)可以看做自由空間損耗模型，簇間為多徑衰落損耗模型。

E=Elocal+Elong=Et_local+Ec_local+Et_long+Ec_long

(1)

Pt_local=εamp_localRbd2

(2)

Pt_long=εamp_longRbd4

(3)

式中：Elocal是簇內(nèi)數(shù)據(jù)傳輸能耗；Elong是簇間數(shù)據(jù)傳輸能耗；Et_local和Ec_local分別表示本地?cái)?shù)據(jù)傳輸及電路能耗；Et_long和Ec_long分別表示遠(yuǎn)程數(shù)據(jù)傳輸及電路能耗。式(2)表示本地?cái)?shù)據(jù)傳輸?shù)陌l(fā)射功率，εamp_local是本地自由空間模型獲得一定信噪比時(shí)的發(fā)射功率，功率乘以發(fā)射時(shí)間就是能耗。為了保證簇頭和協(xié)作節(jié)點(diǎn)可靠接收數(shù)據(jù)，d是到簇頭和協(xié)作節(jié)點(diǎn)中最大的距離。式(3)是遠(yuǎn)程發(fā)射數(shù)據(jù)時(shí)每比特?cái)?shù)據(jù)消耗的能量，εamp_long為簇間遠(yuǎn)程多徑衰落模型獲得一定信噪比時(shí)的發(fā)射功率。

Et_long,h+Ect×Mth

(4)

2 基于改進(jìn)蟻群算法高能效協(xié)作傳輸策略的描述

2.1 I-CoopACO算法描述

LEACH算法采用單跳傳輸數(shù)據(jù)，當(dāng)距離較遠(yuǎn)時(shí)，能耗較高。因此，一些算法采用單跳和多跳結(jié)合的方式傳輸數(shù)據(jù)，在這些算法中，中繼節(jié)點(diǎn)選擇和中繼對轉(zhuǎn)發(fā)數(shù)據(jù)的壓縮融合與多跳的跳數(shù)及距離有很大的關(guān)系[8]，滿足一定條件下，節(jié)省能耗。在傳感器網(wǎng)絡(luò)中，為了全方位收集環(huán)境信息，節(jié)點(diǎn)密度一般情況下較高，比較容易選擇出協(xié)作節(jié)點(diǎn)構(gòu)成虛擬MIMO，利用協(xié)作MIMO技術(shù)的優(yōu)勢，當(dāng)傳輸距離較遠(yuǎn)時(shí)，簇間多跳和協(xié)作MIMO結(jié)合[9]可以大幅度降低數(shù)據(jù)傳輸能耗，提高數(shù)據(jù)傳輸效率。本文提出的基于改進(jìn)蟻群算法的高能效WSN協(xié)作傳輸策略中，基站首先通過GPS或者其他定位措施對感知區(qū)域中的節(jié)點(diǎn)做定位，然后發(fā)送位置信息告知每一個(gè)感知節(jié)點(diǎn)。感知節(jié)點(diǎn)收到基站發(fā)送的其他節(jié)點(diǎn)位置信息后，對每一個(gè)節(jié)點(diǎn)來說，要完成本地傳輸和遠(yuǎn)程傳輸以將數(shù)據(jù)傳輸?shù)交?。具體算法分為成簇階段和穩(wěn)定傳輸階段。

1)成簇階段

隨機(jī)輪詢選擇簇頭，每一輪網(wǎng)絡(luò)產(chǎn)生統(tǒng)一的改進(jìn)閾值，每個(gè)節(jié)點(diǎn)隨機(jī)選擇0～1之間的值，然后與閾值相比，如果小于閾值，則為簇首，否則，不是簇首節(jié)點(diǎn)。其他節(jié)點(diǎn)根據(jù)接收到的簇首廣播信號(hào)強(qiáng)度加入簇，并調(diào)整簇分布，而后完成分簇。最后，簇首節(jié)點(diǎn)廣播利用TDMA機(jī)制分配的數(shù)據(jù)發(fā)送時(shí)間片，避免簇內(nèi)數(shù)據(jù)傳輸發(fā)生碰撞，其他成員節(jié)點(diǎn)計(jì)算剩余能量和傳輸功耗的比值，選擇值較大的作為遠(yuǎn)程傳輸?shù)膮f(xié)作節(jié)點(diǎn)。

2)穩(wěn)定傳輸階段

在數(shù)據(jù)穩(wěn)定傳輸階段，感知節(jié)點(diǎn)將收集到的數(shù)據(jù)發(fā)送給簇頭，簇頭將接收到的數(shù)據(jù)和自己感知到的數(shù)據(jù)進(jìn)行壓縮融合，利用改進(jìn)蟻群算法搜索中繼節(jié)點(diǎn)，然后更新路由表。本地傳輸中，感知節(jié)點(diǎn)將感知信息通過廣播方式以距離簇頭和協(xié)作節(jié)點(diǎn)中最遠(yuǎn)的距離進(jìn)行廣播，使得協(xié)作域節(jié)點(diǎn)都收到相同數(shù)據(jù)，然后通過并行的獨(dú)立信道發(fā)送數(shù)據(jù)。

2.2 I-CoopACO算法模型的優(yōu)化

1)成簇過程改進(jìn)

2)多跳路由優(yōu)化

蟻群算法[11-13]是一個(gè)啟發(fā)式解決復(fù)雜優(yōu)化問題的算法。螞蟻留下化學(xué)物質(zhì)信息素，這些信息素可以被其他螞蟻感知到，同時(shí)影響著其他螞蟻的行為，當(dāng)每一個(gè)螞蟻釋放信息素后，在最常經(jīng)過的路徑上，信息素的濃度就會(huì)增長得最快，濃度越來越大，最終，這條路徑被其他螞蟻選擇的概率就會(huì)越來越大。這個(gè)尋找最優(yōu)路徑的過程可以表示為

(5)

τij(t+Δt)=(1-ρ)τij(t)+Δτij

(6)

(7)

(8)

(9)

3 算法仿真及性能評估

為了驗(yàn)證本文提出算法和模型的有效性，在計(jì)算機(jī)上進(jìn)行仿真，與其他經(jīng)典算法進(jìn)行比較。假設(shè)感知節(jié)點(diǎn)一次性布置在感知區(qū)域中，區(qū)域邊長為M=100 m的正方形，節(jié)點(diǎn)數(shù)n=200， 基站位置為(50,-120)，數(shù)據(jù)采集速率為1 Mbit/s，數(shù)據(jù)長度l=2 000 bit，控制包長度為100 bit，初始能量Eo=1 J， 壓縮每比特?cái)?shù)據(jù)能耗為Eda=5 nJ/bit，數(shù)據(jù)壓縮比為0.1，電路發(fā)射和接收每比特?cái)?shù)據(jù)能耗為Ect=Ecr=50 nJ/bit，每比特單跳傳輸數(shù)據(jù)獲得一定接收信噪比的能耗為εamp_long_single=0.02 pJ/bit/m4。蟻群算法中，螞蟻數(shù)為50，α=1.5,β=0,ρ=0.3,Q=1。如果不再說明，本文其他仿真中條件不變，網(wǎng)絡(luò)的工作壽命用第一個(gè)節(jié)點(diǎn)死亡輪數(shù)來表示。

在LEACH算法中，每一輪分簇?cái)?shù)目不同，能耗情況不同，當(dāng)簇頭概率為10%時(shí)，能耗最低。但是，實(shí)際中，每輪選擇出來的簇頭個(gè)數(shù)并不一定是最優(yōu)值，而是一個(gè)變化的值。LEACH的閾值選擇簇頭算法導(dǎo)致每輪簇頭個(gè)數(shù)在數(shù)學(xué)期望上下波動(dòng)變化，當(dāng)波動(dòng)變化大時(shí)將造成系統(tǒng)性能驟降，生存期大幅縮短。因此，對簇規(guī)模的改善十分重要。如圖2所示為改進(jìn)成簇算法后的簇分布圖，大圓圈表示簇頭，離它較近的小圓圈表示協(xié)作節(jié)點(diǎn)，相同點(diǎn)型表示同一個(gè)簇，可以看出，在當(dāng)前輪中，分成了11個(gè)簇，每一個(gè)簇頭距離其他簇都在最優(yōu)間隔R以外，簇的分布比較均勻。

圖2 改進(jìn)成簇算法后的簇分布

在100 m×100 m的感知范圍內(nèi)，原始蟻群算法的路徑優(yōu)化結(jié)果如圖3所示。如圖3a所示，其尋找的最優(yōu)路徑是基于遍詢所有節(jié)點(diǎn)，且其總距離最短，圖3b中也說明了這點(diǎn)。迭代5次左右，算法找到了最短距離路徑，收斂速度快，獲得了遍尋所有節(jié)點(diǎn)最短距離的局部最優(yōu)解。但是也可以看到，其平均距離還是沒有收斂，最短距離不一定是全局的最短距離。

圖3 原始蟻群算法最優(yōu)路徑

改進(jìn)蟻群算法的路徑優(yōu)化結(jié)果如圖4所示。如圖4a所示，其尋找的最優(yōu)路徑是基于將每個(gè)候選簇頭節(jié)點(diǎn)的剩余能量和傳輸功耗引入到信息素更新方法后得到的最優(yōu)路徑。在圖4b中可以看到，獲得了最小的傳輸功耗。迭代7次左右，找到了最小傳輸功耗的路徑，收斂速度快。在引入節(jié)點(diǎn)剩余能量和傳輸功耗影響后，獲得了最小傳輸能耗的局部最優(yōu)路徑解，降低了節(jié)點(diǎn)的傳輸功耗，同時(shí)均衡了網(wǎng)絡(luò)所有節(jié)點(diǎn)的剩余能量，避免出現(xiàn)死亡空洞。

圖4 改進(jìn)蟻群算法最優(yōu)路徑

如圖5所示，比較了網(wǎng)絡(luò)采用LEACH、CoopLEACH、I-CoopLEACH、CoopACO和 I-CoopACO傳輸算法的工作輪數(shù)。從圖中可以看出，CoopLEACH的工作壽命是LEACH的10倍左右，這是因?yàn)閰f(xié)作技術(shù)能夠在遠(yuǎn)距離傳輸時(shí)獲得多徑增益，平均能耗較低，CoopLEACH的平均能耗為0.058 8 J。I-CoopLEACH與CoopLEACH相比，工作壽命延長了500多輪，這是由于I-CoopLEACH算法中，改進(jìn)的成簇算法減少了匯聚數(shù)據(jù)時(shí)的傳輸功耗，均衡了負(fù)載。在CoopACO算法中，使用未改進(jìn)的蟻群算法搜索簇間多跳路徑，減少了能量消耗，延長了工作壽命。在優(yōu)化信息素更新方式的I-CoopACO算法中，第一個(gè)節(jié)點(diǎn)死亡輪數(shù)大大延緩，1 966輪之后，第1個(gè)節(jié)點(diǎn)才開始死亡，而CoopLEACH算法到1 192輪就開始死亡，I-CoopLEACH算法到1 563輪開始死亡，CoopACO到1 750輪開始死亡，可以看出I-CoopACO算法的成簇機(jī)制使分簇更加均勻，簇的數(shù)目也更優(yōu)，搜索的中繼節(jié)點(diǎn)轉(zhuǎn)發(fā)數(shù)據(jù)時(shí)消耗能量更少，更加均衡，選擇了更小能耗的路徑傳輸數(shù)據(jù)，每一輪網(wǎng)絡(luò)平均消耗能量為0.045 8 J，表明I-CoopACO算法的數(shù)據(jù)傳輸策略使得每一輪的網(wǎng)絡(luò)耗能更少，更加均衡，節(jié)點(diǎn)死亡速度更小，與CoopLEACH相比，延長了64.93%的網(wǎng)絡(luò)工作壽命。

圖5 不同算法的網(wǎng)絡(luò)工作壽命比較

4 結(jié)論

本文對已有的數(shù)據(jù)傳輸策略進(jìn)行了分析改進(jìn)，提出了一種基于改進(jìn)蟻群算法高能效協(xié)作傳輸策略I-CoopACO算法，這個(gè)算法優(yōu)化了成簇過程和簇分布，利用協(xié)作MIMO技術(shù)發(fā)送數(shù)據(jù)，在選擇下一跳節(jié)點(diǎn)時(shí)，以節(jié)點(diǎn)剩余能量和傳輸功耗構(gòu)建啟發(fā)因子，選擇出更優(yōu)的中繼節(jié)點(diǎn)，保證了數(shù)據(jù)傳輸過程能耗最低，使得網(wǎng)絡(luò)能量消耗更加均衡，延長了網(wǎng)絡(luò)工作壽命。但是可以看到本文提出的算法，由于需要根據(jù)已知位置信息搜索出能耗最低的路由，導(dǎo)致較高的硬件代價(jià)，降低算法復(fù)雜度以獲得較低的硬件代價(jià)是未來研究的重點(diǎn)。

[1] FENG Daquan，JIANG Chenzi，LIM Gubong，et al. A survey of energy-efficient wireless communications[J]. IEEE Communications Surveys & Tutorials，2013，15(1)：167-178.

[2] HARMS T，SEDIGH S，BASTIANINI F. Structural health monitoring of bridges using wireless sensor networks[J]. IEEE Instrumentation and Measurement Magazine，2010，13(6)：14-18.

[3] ZHANG Yanbing，DAI Huaiyu. Energy-efficiency and transmission strategy selection in cooperative wireless sensor networks[J]. Journal of Communications and Networks，2007，9(4)：473-481.

[4] YI H，HUA Y. Energy planning for progressive estimation in multi-hop sensor networks[J]. IEEE Trans. Signal Processing，2009，57(10)：4052-4065.

[5] HEINZELMAN W B，CHANDRAKASAN A P，BALAKRISHNAN H. An application-specific protocol architecture for wireless micro-sensor networks[J]. IEEE Trans. Wireless Communications，2002，1(4)： 660-670.

[6] CUI SH G，GOLDSMITH A J，BAHAI A. Energy-efficiency of MIMO and cooperative MIMO techniques in sensor networks[J]. IEEE Journal on Selected Areas in Communications，2004，22(6)：1089-1098.

[7] YUN K H. Energy efficient cooperative LEACH protocol for wireless sensor networks[J].Journal of Communications and Networks，2010，12(4)：358-365.

[8] GAO Q，ZUO Y，ZHANG J，et al. Improving energy efficiency in a wireless sensor network by combining cooperative MIMO with data aggregation[J].IEEE Trans. Vehicular Technology，2010，59(8)：3956-3965.

[9] JAYAWEERA S K. Virtual MIMO-based cooperative communication for energy-constrained wireless sensor networks[J]. IEEE Trans. Wireless Communications，2006，5(5)：984-989.

[10] CHENG W Q， XU K R，LIU W，et al. An energy-efficient cooperative MIMO transmission scheme for wireless sensor networks[C]//Proc. International Conference on WiCOM 2006，Networking and Mobile Computing，Wireless Communications. [S.l.]：IEEE Press，2006：22-24.

[11] KWANG M S，SUN W H. Ant colony optimization for routing and load-balancing： survey and new directions，Systems，Man and Cybernetics[J].IEEE Trans. Part A：Systems and Humans，2003，33(5)：560-572.

[12] KIM Y M，LEE E J，PARK H S. Ant colony optimization based energy saving routing for energy-efficient networks[J]. IEEE Communications Letters，2011，15(7)：779-781.

[13] HU X M，ZHANG J. Ant routing optimization algorithm for extending the lifetime of wireless sensor networks[C]//Proc. 2010 IEEE International Conference on Systems Man and Cybernetics(SMC). [S.l.]：IEEE Press，2010：738-744.

李燕龍(1988— )，碩士，主研無線傳感器網(wǎng)絡(luò);

王俊義(1977— )，博士，副教授，主要研究方向?yàn)榫W(wǎng)絡(luò)性能分析與優(yōu)化；

符杰林(1975— )，博士生，副教授，主要研究方向?yàn)闊o線通信、無線傳感網(wǎng)絡(luò)；

仇洪冰(1963— )，博士，博士生導(dǎo)師，教授，主要研究方向?yàn)槌瑢拵ㄐ?、無線傳感器網(wǎng)絡(luò)。

責(zé)任編輯：許 盈

Based Improved Ant Colony Algorithm Energy-efficient WSN Cooperative Transmission Strategy

LI Yanlong, WANG Junyi, FU Jielin, QIU Hongbing

(SchoolofInformationandCommunication,GuilinUniversityofElectronicTechnology,GuangxiGuilin541004，China)

Focusing on the problem of clustering unevenly and energy consumption of data transmission is relatively high for traditional sensor networks, a I-CoopACO (Cooperative transmission scheme based improved Ant Colony Optimal algorithm) algorithm is proposed in this paper. Based on cooperative LEACH techniques, the algorithm improves the process of clustering and makes clustering scale more uniform. In stable transmission stage, it uses the residual energy and data transmission power to build inspiring factor and searches the next hop relay node with improved Ant colony algorithm to obtain the most optimal node. So it makes transmission power lower and energy consumption more balanced. Simulation results show that in the random distribution of sensor networks, I-CoopACO algorithm reduces the transmission energy consumption, balances network load, extends 64.93% working life compared with cooperative LEACH algorithm.

wireless sensor networks; energy-efficient; transmission route; virtual MIMO; ant colony algorithm

【本文獻(xiàn)信息】李燕龍，王俊義，符杰林,等.基于改進(jìn)蟻群算法的高能效WSN協(xié)作傳輸策略[J].電視技術(shù),2015，39(11).

國家自然科學(xué)基金項(xiàng)目(61172054；61371107；61261017；61362006)；廣西自然科學(xué)基金項(xiàng)目(2013GXNSFAA019334)

TN915

A

10.16280/j.videoe.2015.11.030

2014-10-12