基于PSO算法和移動Agent的WSN路徑優化研究

張珊靚，趙浩婕

（安陽工學院，河南 安陽 455000）

0 引 言

無線傳感器網絡[1]（wireless sensor network，WSN）即由大量的傳感器節點通過多跳自組織的方式構成的網絡，傳感器節點散布于網絡中，傳感器的功能是感知數據和傳輸數據。目前已有工作證明傳感器傳輸數據耗能比感知數據耗能要大幾個數量級[2]。

傳統的數據傳輸方法通?；贑/S模型，在C/S模型中，傳感器節點被視作C即客戶端，而Sink節點被視作S即服務器。傳感器節點在感知數據后，將數據傳輸給Sink節點進行融合處理。這種方式的缺陷在于所有傳感器都需要將數據發送給Sink節點，導致節點能耗大，同時Sink節點需要接收所有數據并進行融合也導致其能耗大；所以，C/S的數據傳輸方法會導致網絡能耗大，縮短了網絡生命周期。

為了解決C/S模式數據傳輸方法的缺陷，移動Agent[3]被引入用于傳輸節點采集數據。文獻[4]提出一種基于遺傳算法的自適應數據融合算法，使用移動代理到各節點進行數據收集，是否進行數據融合則需比較節點進行數據融合后的能量消耗是否比直接發送數據小來確定。文獻[5]提出了使用蟻群算法來對移動Agent訪問路徑進行優化的方法，在選取路徑時兼顧節點能量消耗以及剩余能量。文獻[6]提出移動代理問題是一個優化問題，并使用混沌搜索的全局空間能力和模擬退火算法的快速尋優能力來進行路由優化。

上述方法均采用啟發式方法和移動Agent來實現對無線傳感器的傳統數據傳輸機制進行改進和優化，但由于上述啟發式算法均需知道網絡的全局信息，且依賴于網絡規模的大小；所以，本文提出了一種先確定可訪問集，再使用PSO算法[7-8]的路徑優化方法，具有收斂速度快、全局尋優能力強等優點。

1 移動Agent概述及網絡模型

1.1 移動Agent概述

移動Agent由Sink節點（或者其他處理節點）發出，攜帶著處理代碼，可以自主地從網絡中的一個傳感器節點遷移到另一個，并進行節點訪問，獲取節點采集數據，使用處理代碼處理數據，進行數據融合，并將融合后的數據發送給Sink節點。

移動Agent的引入解決了節點需要將采集到的數據發送給Sink節點所耗費的大量能量，結合了分布式計算和人工智能的優勢，能夠有效地均衡節點能耗，減少網絡流量。

1.2 基于移動Agent的網絡模型

無線傳感器網絡的模型通常包含Sink節點、傳感器節點、互聯網以及遠程監控終端。網絡中的傳感器節點將采集的數據發送給Sink節點，Sink節點再通過互聯網將數據發送給遠程控制終端。

基于移動Agent的網絡模型在此基礎上增加了移動Agent，移動Agent由Sink節點發出，在網絡中的傳感器節點之間進行遷移，采集并融合傳感器節點收集到的數據，最終將處理結果發送給Sink節點，其網絡模型如圖1所示。

圖1 基于移動Agent的網絡模型

2 基于移動Agent的路徑優化研究

2.1 基于移動Agent和PSO的優化原理

基于移動Agent的路徑優化方法主要可以從以下3個方面來考慮：

（1）為了減少Agent融合數據量，提高融合效率，首先需要確定移動Agent可訪問節點集合，將一些冗余節點和失效節點從可訪問節點集合中刪除；

（2）對由第1步得出的可訪問節點集合任意指定一條移動Agent的遍歷路徑；

（3）從第2步中確定的初始路徑出發，使用粒子群算法尋優，計算適應度函數，直到尋找到最優路徑為止。

2.2 移動Agent可訪問節點集合

首先定義傳感器節點的數據包結構，數據包包含節點ID和數據內容兩個部分。Sink節點的數據包結構為一個鏈表和一個可訪問節點集合：鏈表中每個元素為一個傳感器節點數據包結構，即傳感器節點ID和數據內容；可訪問節點集合為節點ID列表，其初始值為空。

可訪問節點獲取算法步驟如下：

步驟1：初始化，對所有傳感器節點分配全網唯一的節點ID；

步驟2：Sink節點在全網廣播數據采集請求；

步驟3：收到數據采集請求的節點將采集數據發送給Sink節點；

步驟4：Sink節點收到節點數據采集信息后，向發送節點發送一個默認的確認包，并比較該數據是否已經在鏈表的數據包中出現過，如果出現過，則進入步驟5；否則，將其加入到可訪問節點集合中去；

步驟5：循環執行2～4直到某個預設的時間閥值為止，此時，如有部分節點始終沒有反應，則這些節點被視為失效節點；

步驟6：Sink節點中的可訪問節點集合即為移動Agent將要遷移并進行數據收集和融合的節點集合，算法結束。

2.3 初始訪問路徑

訪問路徑的優劣程度通過適應度來衡量，適應度函數為

式中：β、γ——調節系數；

f（pi）——遷移路徑r中節點pi的融合耗能，表達式見式（2）；

t（pi）——節點pi的數據傳輸耗能，可以表示為式（3）。

式中：dMa——移動代理本身攜帶的數據；

Δd——移動代理遷移到傳感器節點pi時的數據增量；

Eds——單位數據融合耗能。

式中：distpipj——移動Agent從傳感器節點pi遷移到

傳感器節點pj之間的距離。

初始訪問路徑的選擇即從可訪問節點集合中選取任意一條路徑，并根據式（1）計算其適應度。

2.4 PS0優化移動Agent遷移路徑

PS0優化移動Agent遷移路徑算法步驟為：

步驟1：初始化，設定粒子個數為N，粒子的空間維數即為可訪問節點集合中的節點個數M，粒子初始位置即為通過2.3所確定的初始路徑，個體極值和全局極值均為當前粒子位置

輸入：k=1≤kmax表示當前迭代次數；

輸出：具有滿足式（1）的有最大適應度的可訪問節點序列。

步驟2：N個粒子從初始位置出發，進行迭代；

步驟3：第i個粒子的位置和速度可以表示為式（4）和式（5），并根據式（6）更新第 i個粒子的位置，根據式（7）更新第i個粒子的速度，式（7）中的和分別表示第k次迭代中的個體極值和N個粒子的全局極值；

步驟4：根據粒子的新位置信息結合式（1）計算新適應度，將計算所得的新適應度與粒子的個體極值即相比較，如果高于，則當前位置復制給；

步驟5：對于N個粒子，如果其所在位置對應的適應度高于全局極值，則更新為當前具有最優適應度的粒子位置；

步驟6：若迭代次數k已為最大值kmax，則轉入步驟7，否則轉入步驟3粒子開始繼續尋優；

步驟7：算法結束，粒子所在位置即為M個可訪問節點的訪問序列。

3 仿真實驗

仿真實驗環境：無線傳感器區域為200m×200m的正方形區域，節點隨機散步在網絡區域中，其數量約為300個，節點通信半徑為40 m，匯聚節點位于正方形區域左上角，采用Matlab仿真工具，比較了文中算法和文獻[4]中的遺傳算法及文獻[6]中的蟻群算法在網能耗差異，如圖2所示。

從圖2中可以看出，由于本文首先確定了可訪問節點集合，并采用PSO優化方法對節點訪問序列進行尋優，所以網絡傳輸耗能小于采用遺傳算法和蟻群算法得到的結果，證明文中方法的優越性。

圖2 不同算法總能量消耗對比

4 結束語

在無線傳感器網絡中，由于節點能量有限，而節點傳輸能量需要耗費大量能量導致節點過早死亡。為了更好地均衡網絡能耗耗費，本文提出了一種移動代理對各傳感器節點數據進行處理和融合的方法，首先取得可訪問節點集，然后通過PSO算法對可訪問節點集中的節點訪問序列進行尋優。實驗表明本方法所需網絡傳輸耗能較采用遺傳算法和蟻群算法所需能耗小。

[1]王偉東，朱清新.無線傳感器網絡中一種層次分簇算法及協作性分析[J].軟件學報，2006，17（5）：1157-1167.

[2]Kyildiz I F，Su W，Sankarasubramaniam Y，et al.Wireless sensor networks:a survey [J].Computer Networks，2002，38（4）：393－422.

[3]周四望，林亞平，聶雅琳，等.無線傳感器網絡中基于數據融合的移動代理曲線動態路由算法研究[J].計算機學報，2007，30（6）：894－904.

[4]王天荊，楊震，胡海峰.基于遺傳算法的無線傳感器網絡自適應數據融合路由算法[J].電子與信息學報，2007，29（9）：2244-2247.

[5]鄭巍，劉三陽，寇曉麗.動態傳感器網絡移動代理路由算法[J].控制與決策，2010，25（7）：1035-1039.

[6]周強，崔遜學，陳桂林.基于移動代理的大規模無線傳感器網絡路由優化算法[J].計算機應用，2011，31（7）：1924-1927.

[7]Eberhart R，Kennedy J.A new optimizer usingparticle sw arm theory[C]∥Proceedings of the Sixth International Symposium onMicroMachineandHumanScience，1995：39-43.

[8]Kennedy J，Eberhart R C，Shi Y.Swarm Intelligence[M].San Francisco：Morgan Kaufman Publishers，2001：287-288.