基于PSO算法和移動Agent的WSN路徑優(yōu)化研究

張珊靚，趙浩婕

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

0 引 言

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

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

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

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

1 移動Agent概述及網(wǎng)絡模型

1.1 移動Agent概述

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

移動Agent的引入解決了節(jié)點需要將采集到的數(shù)據(jù)發(fā)送給Sink節(jié)點所耗費的大量能量，結合了分布式計算和人工智能的優(yōu)勢，能夠有效地均衡節(jié)點能耗，減少網(wǎng)絡流量。

1.2 基于移動Agent的網(wǎng)絡模型

無線傳感器網(wǎng)絡的模型通常包含Sink節(jié)點、傳感器節(jié)點、互聯(lián)網(wǎng)以及遠程監(jiān)控終端。網(wǎng)絡中的傳感器節(jié)點將采集的數(shù)據(jù)發(fā)送給Sink節(jié)點，Sink節(jié)點再通過互聯(lián)網(wǎng)將數(shù)據(jù)發(fā)送給遠程控制終端。

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

圖1 基于移動Agent的網(wǎng)絡模型

2 基于移動Agent的路徑優(yōu)化研究

2.1 基于移動Agent和PSO的優(yōu)化原理

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

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

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

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

2.2 移動Agent可訪問節(jié)點集合

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

可訪問節(jié)點獲取算法步驟如下：

步驟1：初始化，對所有傳感器節(jié)點分配全網(wǎng)唯一的節(jié)點ID；

步驟2：Sink節(jié)點在全網(wǎng)廣播數(shù)據(jù)采集請求；

步驟3：收到數(shù)據(jù)采集請求的節(jié)點將采集數(shù)據(jù)發(fā)送給Sink節(jié)點；

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

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

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

2.3 初始訪問路徑

訪問路徑的優(yōu)劣程度通過適應度來衡量，適應度函數(shù)為

式中：β、γ——調(diào)節(jié)系數(shù)；

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

t（pi）——節(jié)點pi的數(shù)據(jù)傳輸耗能，可以表示為式（3）。

式中：dMa——移動代理本身攜帶的數(shù)據(jù)；

Δd——移動代理遷移到傳感器節(jié)點pi時的數(shù)據(jù)增量；

Eds——單位數(shù)據(jù)融合耗能。

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

傳感器節(jié)點pj之間的距離。

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

2.4 PS0優(yōu)化移動Agent遷移路徑

PS0優(yōu)化移動Agent遷移路徑算法步驟為：

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

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

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

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

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

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

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

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

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

3 仿真實驗

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

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

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

4 結束語

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

[1]王偉東，朱清新.無線傳感器網(wǎng)絡中一種層次分簇算法及協(xié)作性分析[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]周四望，林亞平，聶雅琳，等.無線傳感器網(wǎng)絡中基于數(shù)據(jù)融合的移動代理曲線動態(tài)路由算法研究[J].計算機學報，2007，30（6）：894－904.

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

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

[6]周強，崔遜學，陳桂林.基于移動代理的大規(guī)模無線傳感器網(wǎng)絡路由優(yōu)化算法[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.