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

和 煦，寧中正，楊小勇

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

無線傳感器網(wǎng)絡(luò)(Wireless Sensor Network,WSN)是在監(jiān)測區(qū)域范圍內(nèi)部署大量能量有限的傳感器節(jié)點，并以無線通信方式形成的自組織網(wǎng)絡(luò)系統(tǒng)[1]，其在軍事、農(nóng)業(yè)、醫(yī)療以及智能家居等方面都有廣泛的應用。但是，存在的主要問題之一是在能量有限的情況下延長網(wǎng)絡(luò)的生命周期[2]?？紤]路由協(xié)議是WSN能耗的主要構(gòu)成[3]，因此通過優(yōu)化路由協(xié)議延長網(wǎng)絡(luò)的生命周期是一種重要且高效的節(jié)能方式。

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

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

1 系統(tǒng)模型

1.1 能耗模型

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

當發(fā)送數(shù)據(jù)為l，傳輸距離為d時，能量消耗公式為

(1)

(2)

接收lbit數(shù)據(jù)時的能量消耗公式為

ER(l)=lEe

(3)

若某簇內(nèi)節(jié)點總數(shù)為n，每個節(jié)點傳輸lbit數(shù)據(jù)到簇頭時，簇頭數(shù)據(jù)融合的能量消耗公式為

EF(l,n)=nlEf

(4)

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

1.2 網(wǎng)絡(luò)模型

網(wǎng)絡(luò)模型由一個基站、多個簇頭節(jié)點以及多個成員節(jié)點組成，分簇網(wǎng)絡(luò)模型如圖2所示。

圖2 分簇網(wǎng)絡(luò)模型

對分簇網(wǎng)絡(luò)做如下規(guī)定。

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

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

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

4)簇頭節(jié)點接收簇內(nèi)所有成員節(jié)點采集的檢測數(shù)據(jù)，并對這些數(shù)據(jù)進行融合，傳輸?shù)交尽?/p>

2 正弦余弦算法

2.1 標準的正弦余弦算法

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

(5)

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

(6)

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

2.2 改進的正弦余弦算法

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

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

(7)

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

Xij(t+1)=

(8)

3 基于ISCA的分簇路由協(xié)議

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

3.1 簇頭初始化

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

假設(shè)網(wǎng)絡(luò)覆蓋區(qū)域范圍內(nèi)傳感器節(jié)點總數(shù)為N，每輪在其中選舉G個簇頭，基站根據(jù)所有節(jié)點的能量信息，計算當前剩余能量最大的節(jié)點，并從其余節(jié)點中選取能量大于或等于最大能量一半的節(jié)點構(gòu)成一個集合，即

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

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

3.2 適應度函數(shù)

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

(9)

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

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

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

3.3 基于ISCA優(yōu)化簇頭選舉的具體步驟

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

圖3 ISCA優(yōu)化簇頭選舉的流程

具體步驟如下。

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

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

步驟3對于每個個體，計算網(wǎng)絡(luò)中所有成員節(jié)點到每個個體中簇頭節(jié)點的距離，并選擇最短距離的簇頭入簇。

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

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

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

4 算法仿真與分析

4.1 仿真環(huán)境設(shè)置

所有的仿真均采用MATLAB 8.5軟件編程，在Intel Core i7 CPU，8 GB內(nèi)存，2.6 GHz主頻的計算機上實現(xiàn)。在200 m×200 m的網(wǎng)絡(luò)覆蓋區(qū)域內(nèi)隨機布設(shè)200個傳感器節(jié)點，基站的坐標為(100,250)m，簇頭的選舉概率為0.05，各節(jié)點的初始能量均為0.5 J，數(shù)據(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。算法的最大迭代次數(shù)T為20，種群規(guī)模M為15，路由協(xié)議更新的最大輪數(shù)rmax為1 100輪，最大慣性權(quán)重和最小慣性權(quán)重分別為1.0和0.3，常數(shù)a取值為2；λ1、λ2、λ3的取值分別為0.35、0.35、0.3。

4.2 仿真結(jié)果與分析

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

圖4 網(wǎng)絡(luò)中節(jié)點和基站的分布情況

圖5 LEACH協(xié)議運行到800輪節(jié)點的分布狀態(tài)

圖6 CRISCA協(xié)議運行到800輪節(jié)點的分布狀態(tài)

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

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

圖7 網(wǎng)絡(luò)的生命周期對比

5 結(jié)語

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