基于改進正弦余弦算法的WSN分簇路由協議

和 煦，寧中正，楊小勇

(1.西安郵電大學 通信與信息工程學院，陜西 西安 710121； 2.國家無線電頻譜管理研究所，陜西 西安 710061)

無線傳感器網絡(Wireless Sensor Network,WSN)是在監測區域范圍內部署大量能量有限的傳感器節點，并以無線通信方式形成的自組織網絡系統[1]，其在軍事、農業、醫療以及智能家居等方面都有廣泛的應用。但是，存在的主要問題之一是在能量有限的情況下延長網絡的生命周期[2]。考慮路由協議是WSN能耗的主要構成[3]，因此通過優化路由協議延長網絡的生命周期是一種重要且高效的節能方式。

低功耗自適應集簇分層型(Low Energy Adaptive Clustering Hierarchy,LEACH)協議是最經典的路由協議，其將整個網絡的生命周期分為多個輪，在每輪中先隨機選舉簇頭，簇頭接收簇內所有成員節點采集的環境檢測數據，進行數據融合，再傳輸到基站?？紤]簇頭選舉的隨機性，容易導致能量較低的節點被選為簇頭且不能均勻分布在整個網絡中，出現網絡能耗不均衡現象[4]。針對經典LEACH協議簇頭選舉的不足，文獻[5]提出了一種自適應簇頭輪換機制，提高了網絡壽命和能量利用率。文獻[6]提出了一種改進的路由協議，采用節點的剩余能量、鄰居節點的個數以及與基站之間距離這3個因子改進閾值的計算公式，有效降低了網絡的能量消耗。文獻[7]提出了一種能量均衡的成簇協議，分別對成簇階段的簇頭選舉公式和穩定階段的通信周期進行了改進，平衡了整個網絡的能量消耗。此外，國內外學者也在一些群體智能優化算法的基礎上提出了各類改進的分簇路由協議，如基于引力搜索算法的分簇路由協議[8]，采用引力搜索算法對網絡簇頭的通信鏈路進行規劃，同時，根據普通節點與高能節點能量的差異進行分簇，較好地均衡了節點的能耗。基于粒子群優化算法的分簇路由協議[9]，利用粒子群優化算法選出最優簇頭，提高了網絡壽命?；谖灮鹣x算法的分簇路由協議[10]，通過自組織映射神經網絡和螢火蟲算法求最優解，從而獲得合適的分簇，在一定程度上改善了網絡存活時間，但是上述研究在分簇階段均未考慮簇頭與基站之間的距離因素，簇頭傳輸數據到基站可能消耗較多的能量。

針對經典LEACH協議中隨機選舉簇頭的不足，擬提出一種基于改進正弦余弦算法的分簇路由協議(Clustering Routing Protocol Based On Improved Sine Cosine Algorithm,CRISCA)，引入慣性權重因子改進正弦余弦算法，并在簇頭選舉時，綜合考慮各節點之間、節點與基站之間的距離以及節點的剩余能量因素構建適應度函數。通過求得適應度函數的最優解選舉最優簇頭，降低節點的能耗，延長網絡的生命周期。

1 系統模型

1.1 能耗模型

采用文獻[11]中常用的一階無線電模型作為該WSN的能耗模型，如圖1所示。

當發送數據為l，傳輸距離為d時，能量消耗公式為

(1)

(2)

接收lbit數據時的能量消耗公式為

ER(l)=lEe

(3)

若某簇內節點總數為n，每個節點傳輸lbit數據到簇頭時，簇頭數據融合的能量消耗公式為

EF(l,n)=nlEf

(4)

其中：Ee為傳感器處理單位數據時的能量消耗；εs和εm分別為自由空間模型和多徑衰落模型中功率放大器能量消耗的比例系數；d0為距離閾值；Ef為數據融合的能耗系數。

1.2 網絡模型

網絡模型由一個基站、多個簇頭節點以及多個成員節點組成，分簇網絡模型如圖2所示。

圖2 分簇網絡模型

對分簇網絡做如下規定。

1)所有節點的初始能量均相同，且不能補充能量，基站的能量視為無限。

2)所有節點都具有唯一的身份標識號(Identity Document,ID)，且均有可能成為簇頭。

3)所有節點和基站部署之后均不能改變位置，但能感知接收信號的強度計算彼此之間的距離。

4)簇頭節點接收簇內所有成員節點采集的檢測數據，并對這些數據進行融合，傳輸到基站。

2 正弦余弦算法

2.1 標準的正弦余弦算法

正弦余弦算法[12](Sine Cosine Algorithm,SCA)是一種新的群體智能優化算法，具有參數少、結構簡單以及易實現等特點，因此，利用正弦和余弦函數的波動性和周期性進行迭代尋優。假設種群規模為M，即包含M個個體，每個個體的維度為D，那么，個體i在第j維的空間位置表示為Xij，i∈{1,2,…,M}，j∈{1,2,…,D}。首先，在解空間內隨機產生M個個體的初始位置，對應種群規模的大小。然后，計算每個個體的適應度值，并記錄當前最優個體位置。最后，循環至滿足終止條件，輸出最優解。在每次迭代中，個體位置的更新表達式為

(5)

其中：Xij(t)為個體i在第t次迭代時的位置在第j維的分量；Pj(t)為第t次迭代種群當前最優個體在第j維的分量；r2∈[0,2π]、r3∈[0,2]和r4∈[0,1]為3個隨機參數；r1為控制參數，隨著迭代次數的增加從a遞減到0，可表示為

(6)

其中：a為常數；t為當前的迭代次數；T為最大迭代次數。

2.2 改進的正弦余弦算法

慣性權重主要控制歷史因素對當前狀態的影響程度[13]。標準的SCA中慣性權重默認為1，導致算法在迭代初期保持較大范圍的全局搜索，而在后期搜索個體易發生位置的震蕩。

給每次迭代的所有個體分別引入不同大小的慣性權重，按照每個個體的適應度函數值進行從小到大的排序，適應度值越小表明個體離最優位置越近，此時讓個體擁有較小的慣性權重，增強局部搜索能力。反之，適應度值越大表明個體離最優位置越遠，此時讓個體擁有較大的慣性權重，增強全局搜索能力，讓個體向最優位置靠近。同時，采用0～π/2之間的余弦函數控制慣性權重的變化，該函數在該區間內是單調遞減的，且在初期的遞減速度較慢，能保證搜索初期保持較大的慣性權重，且不會過早進入局部搜索，避免早熟，后期保持較小的慣性權重。此慣性權重表示為

(7)

其中：wmax和wmin分別為慣性權重的最大值和最小值；orderi為第i個個體按適應度值由小到大排序的索引。因此，改進的正弦余弦算法(Improved Sine Cosine Algorithm,ISCA)的位置迭代方程由式(5)更新為

Xij(t+1)=

(8)

3 基于ISCA的分簇路由協議

經典LEACH協議主要依據各傳感器節點產生一個(0,1)之間的隨機數是否小于所設的閾值進行簇頭的選舉[14]，但是這種隨機選舉簇頭的方式容易導致能量較低的節點被選為簇頭和簇頭分布不均勻現象。在經典LEACH協議的基礎上采用ISCA算法，依據各節點之間、節點與基站之間的距離以及節點的剩余能量構建適應度函數，確定每輪最佳簇頭的選舉方案。

3.1 簇頭初始化

在ISCA中，采用隨機方式選取候選解集，而經典LEACH協議也采用隨機方式選舉簇頭，容易導致算法陷入局部最優，選舉能量較低的節點成為簇頭節點，導致簇頭過早死亡。為此，在初始化時，對候選簇頭節點的能量進行一定的限制。

假設網絡覆蓋區域范圍內傳感器節點總數為N，每輪在其中選舉G個簇頭，基站根據所有節點的能量信息，計算當前剩余能量最大的節點，并從其余節點中選取能量大于或等于最大能量一半的節點構成一個集合，即

A={E(k):E(k)≥0.5Ekmax|?k,1≤k≤N}

再從集合A中隨機選取G個節點構成一個個體，隨后采用同樣的方法繼續在集合A中選取G個節點，一共進行M次選取，最終生成M組初始簇頭節點集，即M個個體。每個個體代表一種簇頭的選舉方案，個體的維度D均相同，且等于簇頭的數量G，通過適應度函數評價解的質量，選取最大迭代次數后的最優個體，對應簇頭的最佳選取方案。

3.2 適應度函數

簇頭節點主要負責簇內成員節點的數據收集和融合，再將融合后的數據傳送到基站，因此，簇頭節點為網絡中的關鍵節點，比成員節點消耗更多的能量[15]?；谶@一特點，將簇頭節點與成員節點之間的距離，與基站之間的距離以及自身的剩余能量這3個因素加入適應度函數的構建中，作為簇頭選舉的評價指標，此適應度函數方程組表示為

(9)

其中：f1為成員節點nk到對應簇頭hip的最大平均歐式距離因子，hip為第i個個體中的第p個簇頭，|cip|為簇頭hip中包含成員節點的總數；f2為簇頭hip與基站b之間的距離因子；f3為簇頭hip剩余能量的比重因子；λ1,λ2,λ3分別為各因子的權重值，且λ1+λ2+λ3=1。

f1的值越小，說明簇內成員節點到簇頭的平均距離越小，整個簇越緊湊，成員節點傳送數據到簇頭時將消耗較少的能量；f2的值越小，說明較多簇頭分布在離基站較近的位置，簇頭傳送數據到基站時將消耗較少的能量；f3的值越小，說明簇頭的能量比重越大，較高能量的節點被選為簇頭的可能性越大。

將每個個體的位置代入到式(9)的適應度函數中，通過ISCA求解在最大迭代次數之內，適應度函數的最小值，這個最小值對應的解就是最優解，也就是最優個體位置。因此，使適應度函數f值最小的個體所包含的簇頭性能最好，個體的各維度分量對應此輪中各簇頭的位置。

3.3 基于ISCA優化簇頭選舉的具體步驟

通過ISCA求解適應度函數f的最優解，得到每輪的最佳簇頭選舉方案，具體流程如圖3所示。

圖3 ISCA優化簇頭選舉的流程

具體步驟如下。

步驟1計算當前剩余能量最大的節點，并選取剩余能量大于或等于最大剩余能量一半的節點，將其作為候選簇頭集合。

步驟2初始化M個個體，每個個體包含G個候選簇頭節點，即每個個體代表一種簇頭的選舉方案，同時，設置算法的終止條件和最大迭代次數T等參數。

步驟3對于每個個體，計算網絡中所有成員節點到每個個體中簇頭節點的距離，并選擇最短距離的簇頭入簇。

步驟4通過式(9)計算每個個體的適應度值，并記錄當前最優個體位置。

步驟5通過ISCA算法的位置更新式(8)個體的位置。

步驟6判斷是否滿足終止條件，若滿足，則輸出當前最優個體，最優個體中各維度的分量對應各簇頭節點的位置，否則重復步驟3-步驟5。

4 算法仿真與分析

4.1 仿真環境設置

所有的仿真均采用MATLAB 8.5軟件編程，在Intel Core i7 CPU，8 GB內存，2.6 GHz主頻的計算機上實現。在200 m×200 m的網絡覆蓋區域內隨機布設200個傳感器節點，基站的坐標為(100,250)m，簇頭的選舉概率為0.05，各節點的初始能量均為0.5 J，數據包大小為4 kB，控制包大小為100 B，Ee=50 nJ·bit-1，Ef=5nJ·bit-1，εs=10 pJ·(bit·m2)-1，εm=0.001 3 pJ·(bit·m4)-1。算法的最大迭代次數T為20，種群規模M為15，路由協議更新的最大輪數rmax為1 100輪，最大慣性權重和最小慣性權重分別為1.0和0.3，常數a取值為2；λ1、λ2、λ3的取值分別為0.35、0.35、0.3。

4.2 仿真結果與分析

為了對CRISCA協議的優化性能進行評估，在WSN的各參數均相同的前提下，將該協議與經典LEACH協議進行對比仿真，觀察不同輪次中存活節點數的對比。將網絡生命周期分為穩定周期和生存周期。穩定周期定義為網絡開始工作到第一個節點死亡的時間間隔，生存周期定義為網絡開始工作到80%節點死亡的時間間隔，即對應第160個節點的死亡輪數。網絡中各節點和基站的初始分布如圖4所示，圖5和圖6分別是LEACH協議和CRISCA協議運行到800輪的各節點分布狀態。

圖4 網絡中節點和基站的分布情況

圖5 LEACH協議運行到800輪節點的分布狀態

圖6 CRISCA協議運行到800輪節點的分布狀態

圖4-圖6中圓圈代表存活節點，帶星號的圓圈代表簇頭節點，圓點代表死亡節點，叉號代表基站?？梢钥闯觯\行到800輪時，LEACH協議中死亡節點都分布在離基站較遠的區域，且分布較集中，出現能耗不均衡現象。而CRISCA協議中死亡節點分布較均勻，網絡能耗較均衡。此外，LEACH協議和CRISCA協議的死亡節點個數分別為139個和67個。與LEACH協議相比，CRISCA協議將死亡節點的數目降低了51.80%。

圖7是網絡生命周期對比情況，由圖7可以看出，所提CRISCA協議的第一個節點的死亡時間為第493輪，而經典LEACH協議的第一個節點的死亡時間為第311輪。相對于LEACH協議，CRISCA協議將網絡的穩定周期提高了58.52%；同時，CRISCA協議的第160個節點的死亡時間為第1 008輪，而經典LEACH協議的第160個節點的死亡時間為第839輪。相對于LEACH協議，CRISCA協議將網絡的生存周期提高了20.14%。因此，所提的CRISCA協議相對于經典LEACH協議有效延長了網絡的生命周期。

圖7 網絡的生命周期對比

5 結語

針對經典LEACH協議中簇頭選舉的隨機性，提出一種基于改進正弦余弦算法的WSN分簇路由協議CRISCA，設計了關于節點的位置和能量的適應度函數，采用ISCA得到適應度函數的最優解，從而確定每輪的最佳簇頭選舉方案。仿真結果表明，CRISCA協議能較明顯地減少了WSN能量的消耗，延長了WSN的生命周期。