一、 A_Star改進LEACH多跳傳輸協定簡介
1 理論基礎
1.1 A*算法
A算法是一種智能搜尋算法,他在求解問題時所得到的結果會選擇所有路徑中代價最小的節點。
A算法是一種基于啟發式函數的算法,搜尋過程如下:首先建立兩個分别命名為open表和close表的表格,其中open表中存放還未通路并準備擴充的節點,而close表則存放己經拓展過的節點。算法的搜尋過程為:初始化時會将源節點放進open表中,然後依次取出源節點的相鄰節點,假如相鄰節點在close表中,那麼忽略該節點;假如相鄰節點在open表中,則用相鄰節點計算出的啟發函數值替換新open表中對應節點的啟發函數值;假如相鄰節點既不在close表中也不在open表中,那麼将拓展出的節點加入到open表中。
1.2 A維諾圖原理
将空間中的N個點看成是N個生長點,按照最近原則将空間劃分成若幹個部分,使得每一部分隻包含一個生長點,那麼可以将連續的空間劃分成維諾覆寫。維諾圖在區域劃分上有較大的貢獻,維諾圖應用在無線傳感網絡中具有重要的現實意義。
1.3 原始LEACH算法
LEACH協定的工作按照輪的思想進行周期性工作,每一輪由3個步驟組成:
(1)簇首選取。在開始階段,所有的節點的地位都是平等的。簇首的選舉主要是依據普通節點與事先設定的門檻值大小的比較以及該節點在上一輪找那個是否當選過簇首來判斷。具體過程為将節點産生的随機數值rand(θ)與門檻值T(n)進行比較,如果rand(θ)<T(n),那麼該節點就作為簇首。門檻值計算式為
式中,p為簇首在節點中所占的比例大小;r為輪數;G為上一輪非簇首節點集合。在上一輪中當選成簇首的節點在本輪不再擔當簇首,這樣的規定使得沒有擔任過簇首的節點在本輪選舉中成為簇首的幾率增加,有利于網絡節點的均衡;
(2)建立簇。簇首選舉完成後,其通過廣播方式向周圍區域的普通節點發送其當選的ADV消息。接收到ADV消息的普通節點根據所接收到的信号強弱選擇加入相關簇。由于簇首在進行廣播ADV消息時的功率在各個方向上都是相等的,普通節點接收到的ADV信号強度越強代表與簇首的距離越近。成員節點選擇距離最近的簇首并加入可以減少能量的消耗,與此同時向簇首發送包含自資訊的資料包;
圖1 分簇流程圖
(3)資料傳輸。簇劃分完成後,簇内的普通節點将會感覺周圍的環境資訊,簇首會收到簇中成員發送的相關資料。簇首接收這些資料之後,對資料進行分析、去重複和壓縮等操作,并将融合後的資料發送至基站。
1.4 LEACH算法分析
LEACH算法在一定程度上延長了無線傳感網絡的壽命,但仍然存在一些不足,主要表現為:
(1)簇首的選取過程中,采用等機率的方式進行選取,并未考慮到能量和距離問題,進而無法保證簇首的位置,導緻簇首産生集聚現象,加速了節點的死亡;
(2)簇的建立過程中,大量普通節點向新選取的簇首傳輸決定加入哪個簇的消息時,計算過程會消耗電池中的大量能量;
(3)消息傳遞過程中,所有的簇首均采用一跳方式與基站通信,緻使距離基站較遠的節點在通信過程中消耗大量能量,縮短了整個網絡的壽命。
本文針對這3個不足,對LEACH算法進行了改進。
2 改進的LEACH算法
2.1 簇首的選取
正初始狀态下,對每個節點仍然産生一個在[0,1]之間的随機數rand(θ),并使其與門檻值T(n)進行比較。如果rand(θ)<T(n),那麼該節點就作為簇首。在本文算法中,借鑒文獻[15]中使用的權重機率進行普通節點與簇首節點之間的選取,其中普通節點的權重值定義為
簇首節點的權重值定義為
結合節點此時的能量值和其與彙聚節點之間的距離,定義普通節點的門檻值為
定義簇首節點的門檻值為
式中,參數Ec(n)表示節點目前的能量,Ei表示節點的總能量;dc表示目前節點到彙聚節點之間的距離,dm表示所有節點到彙聚節點之間距離的最大值;λ1, λ2≥0為權值,且λ1+λ2=1。通過上述改進,使得離彙聚節點近并且能量多的節點更容易稱為簇首,更具有說服力。
2.2 簇的劃分
使用維諾圖對監測區域進行劃分。為了使與彙聚節點距離較近的節點向其通信,令彙聚節點為一個簇首,那麼n個點和一個彙聚節點共同組成了n+1個節點的無線傳感網絡,維諾圖會将監測區域劃分成n+1個區域,形成n+1個維諾多邊形,那麼每一個維諾多邊形構成一個簇,并且每一個簇内會存在一個簇首。
2.3 資料傳輸方法
對每一個簇首建立一個簇首集合,使用優化的啟發式算法A*将傳統LEACH算法的單跳傳輸模式優化成多跳模式。通過使用這個方法找到相關的轉發節點,由轉發節點将資料傳送到彙聚節點,進而節省能量的消耗。
A算法中,估算路徑總長度的路徑長度評價函數為
F(n)=G(n)+H(n) (6)
式中,G(n)是簇首發送的資料報到達目前簇首n(xn, yn)所消耗的實際能量值;H(n)是啟發函數,其作用是計算從目前簇首n到達彙聚節點(xe,ye)消耗的估計能量值,其表達式為
H(n)=sqrt[(xn−xe)2+(yn−ye)2] (7)
本文對路徑長度評價函數進行改進,改進後的評價函數為
F(n)=αG(n)+βH(n) (8)
式中,α和β均為權重因子。
以下對權重因子大小分類進行讨論:
(1)當α=1時,F(n)=G(n),A算法簡化成為Dijkstra算法。此時的算法沒有了啟發函數H(n)的引導,整個搜尋過程沒有方向性,緻使其在大範圍内搜尋,效率低下;
(2)當α=1,β=1時,此時算法為原始A*算法;
(3)當α=β+q,β=1(q>0)時,F(n)=(1+q)G(n)+H(n),此時的估計函數中,G(n)函數的作用大于啟發函數H(n),是以簇首在向相鄰的簇首發送消息時會更加偏向于離彙聚節點遠的簇首;
(4)當α=1,β=1(q>0)時,F(n)=G(n)+(1+q)H(n),此時的估計函數中,啟發函數H(n)的作用大于G(n)函數,是以簇首在向相鄰的簇首發送消息時會更加偏向于離彙聚節點近的簇首,那麼路徑搜尋的過程将會有更強的方向性,提高了效率。
基于上述分析,本文選取的評價函數為
F(n)=G(n)+(1+q)H(n) (9)
式中,q=e1/NM;e1為移動一次需要消耗的能量;NM 為允許移動的最大值。
二、部分源代碼
close all;
clear;
clc;
%-------------------------------
%現場節點數
n=200;
%n=input('Enter the number of nodes in the space : ');
%Energy Model (all values in Joules)
%初始能量
Eo=0.1;
%Eo=input('Enter the initial energy of sensor nJ : ');
%Field Dimensions - x and y maximum (in meters)
% xm=input('Enter x value for area plot : ');
% ym=input('Enter y value for area plot : ');
xm=100;
ym=100;
%Sink 的 x 和 y 坐标
sink.x=1.5*xm;
sink.y=0.5*ym;
% 節點的最優選舉機率
%成為簇頭
p=0.2;
%Eelec=Etx=Erx
ETX=50*0.000000001;
ERX=50*0.000000001;
%發射放大器類型
Efs=10*0.000000000001;
Emp=0.0013*0.000000000001;
%資料聚合能量
EDA=5*0.000000001; 三、運作結果
四、matlab版本及參考文獻
1 matlab版本
2014a