彭珍瑞，李 輝，董海棠，殷 紅

(蘭州交通大學(xué) 機電工程學(xué)院，甘肅 蘭州730070)

0 引 言

無線傳感器網(wǎng)絡(luò)(WSNs)節(jié)點結(jié)構(gòu)緊湊，重量輕，采用電池供電，一般情況下，節(jié)點分布在不便于維護的惡劣環(huán)境中，必須通過各種手段節(jié)約傳感器節(jié)點能量。另外，盡量減小延遲保證信息獲取的實時性是無線傳感器網(wǎng)絡(luò)的更高性能的要求［1，2］。目前大多數(shù)節(jié)能算法通過分層傳輸數(shù)據(jù)包方法實現(xiàn)，如LEACH 算法［3］、PEGASIS 算法［4］等。相對于節(jié)點到基站間的數(shù)據(jù)直接傳輸，分層方法減小了傳輸距離，降低了能耗，但算法中簇內(nèi)成員在將數(shù)據(jù)送到簇頭節(jié)點時存在排隊競爭，同時多跳發(fā)送數(shù)據(jù)到基站，增大了網(wǎng)絡(luò)的延遲，影響網(wǎng)絡(luò)實時性。和聲搜索(harmony search，HS)算法［5］作為一種新的啟發(fā)式算法，在解決車輛運輸問題［6］、水網(wǎng)設(shè)計［7］等方面都取得了一系列的研究成果。

本文提出一種基于和聲搜索算法的無線傳感器網(wǎng)絡(luò)最優(yōu)路徑選取方法，旨在保證傳輸能耗較小的前提下，降低網(wǎng)絡(luò)的傳輸延遲，完成對能量和傳輸延遲兩方面的優(yōu)化。

1 無線傳感器網(wǎng)絡(luò)模型建立

1.1 路徑傳輸延遲［2］

路徑傳輸延遲是指數(shù)據(jù)包從該路徑的源節(jié)點發(fā)送到該路徑的目的節(jié)點所需要的時間，整個網(wǎng)絡(luò)信息交互導(dǎo)致的通信延遲由四部分組成:處理延遲、排隊延遲、傳輸延遲和傳播延遲。處理延遲由傳感器節(jié)點的處理器決定，傳輸延遲和傳播延遲分別由網(wǎng)絡(luò)帶寬和信號傳播速度決定，這三種網(wǎng)絡(luò)延遲條件恒定，所以，選取相同的權(quán)值因子，將這三種延遲視為只與傳輸路徑的跳數(shù)有關(guān)，通過中間節(jié)點的數(shù)量越多，則延遲越高，即通過單個節(jié)點的網(wǎng)絡(luò)延遲為χ。而減小排隊延遲則需要限制數(shù)據(jù)流盡量少地通過某同一節(jié)點進行中轉(zhuǎn)，減少數(shù)據(jù)傳輸之間的競爭。若節(jié)點等待接收一個數(shù)據(jù)包的網(wǎng)絡(luò)延遲為w，若該節(jié)點有k 個數(shù)據(jù)包等待接收，則網(wǎng)絡(luò)延遲為k·w。假設(shè)網(wǎng)絡(luò)有一條傳輸路徑從V0將數(shù)據(jù)發(fā)送到Vn，路徑P 為(V0，V1，…，Vi，…，Vn)，di為節(jié)點i 與上一個節(jié)點i－1 之間的傳輸延遲，di=χ+kiw，則該路徑P 的網(wǎng)絡(luò)延遲Dp為

假設(shè)從節(jié)點V0將數(shù)據(jù)發(fā)送到Vn有m 條路徑，則每條路徑被選中的概率為

1.2 網(wǎng)絡(luò)能耗模型［1］

無線傳感器網(wǎng)絡(luò)節(jié)點的能耗通常由三部分組成:微控制器單元(MCU)、收發(fā)單元(TCR)、傳感器主板(SB)。每個部分都會有一定的能量消耗，所以，傳感器節(jié)點i 能耗可以表示為

其中，Ei_MCU為傳感器微控制單元消耗能量;Ei_TCR為傳感器收發(fā)單元消耗的能量;Ei_SB為傳感器主板消耗的能量。收發(fā)單元消耗的能量又可以分為接收數(shù)據(jù)的能耗Ei_TCR_RX和發(fā)送數(shù)據(jù)產(chǎn)生的能耗Ei_TCR_TX(di)，所以，選擇路徑P 能量消耗為

2 和聲搜索算法概述

和聲搜索算法將樂器聲調(diào)的和聲類比于優(yōu)化問題中的解向量，對音樂的評價對應(yīng)優(yōu)化問題的目標函數(shù)值［5］。和聲搜索的計算步驟如下:

初始化問題和算法參數(shù)

1)優(yōu)化問題描述如下

其中，f(x)為目標函數(shù)，x 為由決策變量xi構(gòu)成的解向量，i=1，2，…，N，每一個決策的值域為Xi。和聲記憶庫的大小定義為HMS、和聲記憶庫取值概率HMCR、音調(diào)微調(diào)概率PAR、音調(diào)微調(diào)帶寬bw、創(chuàng)作的次數(shù)Tmax。

2)初始化和聲記憶庫

隨機生成HMS 個和聲x1，x2，…，xHMS放入和聲記憶庫，和聲記憶庫形式如下

3)生成一個新的和聲

生成新的和聲x'i=［x'1，x'2，…，x'N］，新的和聲每一個音調(diào)x'i(i=1，2，…，N)通過以下三種機理產(chǎn)生:a.學(xué)習(xí)和聲記憶庫;b.音調(diào)微調(diào);c.隨機選擇音調(diào)。

4)更新和聲記憶庫

對第三步中的新解進行評估，如果優(yōu)于HM 中的函數(shù)值最差的一個，則將新解更新至HM 中。

5)檢查是否達到算法終止條件

重復(fù)步驟第3 步和第4 步，直到創(chuàng)作(迭代)次數(shù)達到Tmax為止。

3 基于和聲搜索算法的無線傳感器網(wǎng)絡(luò)模型求解

3.1 路徑生成的編碼方式

和聲搜索算法應(yīng)用于無線傳感器網(wǎng)絡(luò)數(shù)據(jù)傳輸中，最棘手的問題在于如何將網(wǎng)絡(luò)中的路徑編碼到和聲記憶庫中，同時，編碼方式會對搜索最優(yōu)路徑的有效性有重要影響。本文采用基于優(yōu)先級路徑編碼方式［8］。

假設(shè)網(wǎng)絡(luò)中的節(jié)點數(shù)目為Nmax，同時將網(wǎng)絡(luò)中的節(jié)點編號為將被選入傳輸路徑中的節(jié)點的集合，xk表示和聲記憶庫中的變量，該變量賦值為－2/Nmax～2/Nmax的隨機數(shù)。路徑從節(jié)點1 開始，逐個產(chǎn)生，當每次有新的節(jié)點加入時，該節(jié)點對應(yīng)在的變量將被賦值較大的負優(yōu)先值－2/Nmax，使得該節(jié)點很難被再次選中。具體算法步驟:

2)判斷是否滿足終止條件，如果tk=Nmax或跳轉(zhuǎn)到第4 步;否則k=k+1，跳轉(zhuǎn)到第3 步。

3)路徑拓展，選擇與節(jié)點tk－1有數(shù)據(jù)鏈接，同時節(jié)點優(yōu)先值最大的節(jié)點作為下一跳的節(jié)點xk(tk)=－2/Nmax，跳轉(zhuǎn)到第2 步。

4)路徑完成，如果最后得到的終止節(jié)點為目標節(jié)點，則生成的集合為有效路徑;若終止節(jié)點不為目標節(jié)點，則為無效路徑。

在Matlab 仿真環(huán)境下，以N=20 為例，在100 m×100 m的區(qū)域內(nèi)隨機生成20 個節(jié)點，假定每個節(jié)點的傳輸半徑為R，在此例中R 取50 m，即兩節(jié)點間的距離小于50 m，視為相鄰節(jié)點，數(shù)據(jù)包需要從節(jié)點1 發(fā)送到節(jié)點20，網(wǎng)絡(luò)拓撲結(jié)構(gòu)如圖1 所示。同時隨機生成編碼如表1。

圖1 網(wǎng)絡(luò)拓撲結(jié)構(gòu)圖Fig 1 Structure diagram of network topology

表1 編碼表Tab 1 Encoding table

由拓撲結(jié)構(gòu)可知，節(jié)點1 與節(jié)點2，3，5，6，7 可以產(chǎn)生數(shù)據(jù)通信，比較節(jié)點2，3，5，6，7 對應(yīng)的變量優(yōu)先值，選擇節(jié)點3 作為下一跳的節(jié)點，并將節(jié)點1 的變量賦值為－10，確保其在后面的搜索中不會被選為中轉(zhuǎn)點，同時節(jié)點3 和2，4，5，9，10 有數(shù)據(jù)鏈接，比較后確定節(jié)點4 作為下一跳的中轉(zhuǎn)節(jié)點，依此類推，得到傳輸路徑V={1，3，4，8，17，20}。

3.2 基于和聲搜索的算法流程

由對網(wǎng)絡(luò)模型的分析可知，網(wǎng)絡(luò)建立由網(wǎng)絡(luò)延遲和通信能耗兩方面因素決定，通過用戶對網(wǎng)絡(luò)中延遲和能耗的要求不同，延遲和能耗權(quán)重不同，分別設(shè)為α 和β，α+β=1。和聲向量的質(zhì)量通過目標函數(shù)值來判斷，對低延遲和低功耗的目標定義目標函數(shù)為

考慮延遲和能耗影響，得到算法流程如圖2 所示。

3.3 結(jié)果與分析

圖2 算法流程圖Fig 2 Flow chart of algorithm

在Matlab 環(huán)境下，對100 個節(jié)點的網(wǎng)絡(luò)應(yīng)用和聲搜索算法進行仿真實驗，考慮傳感器相鄰節(jié)點距離R ＜30 m。對延遲和能量消耗兩個目標所占權(quán)重值的不同，分析延遲和能耗對網(wǎng)絡(luò)數(shù)據(jù)傳輸路徑選擇的影響。

分別取α=0，β=1;α=0.5，β=0.5;α=1，β=0;迭代次數(shù)J=1200;圖3(a)為網(wǎng)絡(luò)能耗圖，圖3(b)為網(wǎng)絡(luò)延遲圖。

圖3 網(wǎng)絡(luò)能耗和網(wǎng)絡(luò)延遲圖Fig 3 Diagram of network energy consumption and network delay

由圖3 變化趨勢可以看出:在運行約600 代后，基本可以得到穩(wěn)定的數(shù)據(jù)傳輸路徑。由記錄的數(shù)據(jù)可知，取α=0，β=1，即單獨考慮能耗影響因素，路徑產(chǎn)生的能耗為2 695.86 J，延遲為10.4 s;取α=1，β=0，即單獨考慮降低延遲，導(dǎo)致的延遲為6.2 s，能耗為3 355.73 J;取α=0.5，β=0.5，即給定選擇路徑中能耗及延遲各占50%權(quán)重，則產(chǎn)生的路徑能耗為2 851.1 J，延遲為7.4 s。比較3 組數(shù)據(jù)，當優(yōu)先考慮能耗因素，延遲會相應(yīng)偏高，而優(yōu)先考慮延遲因素，則能耗相對較高，雖然都未達到單方面的最優(yōu)值，但綜合考慮能量消耗和網(wǎng)絡(luò)延遲兩方面因素，可以得到滿足總目標的較優(yōu)傳輸路徑。由此可見，網(wǎng)絡(luò)延遲和網(wǎng)絡(luò)中的能量消耗兩方面因素相互制約，無法同時達到最優(yōu)狀態(tài)，而給延遲和能耗設(shè)定相應(yīng)的權(quán)重值，可以得到用戶所需求的相應(yīng)優(yōu)化路徑。

4 結(jié) 論

本文應(yīng)用和聲搜索算法解決無線傳感器網(wǎng)絡(luò)中低延遲和低能耗的雙目標優(yōu)化問題。分析了網(wǎng)絡(luò)中延遲和能耗模型，同時在找尋最優(yōu)路徑時，采用基于優(yōu)先級的路徑編碼算法，迭代更新和聲記憶庫。在Matlab 仿真環(huán)境下對網(wǎng)絡(luò)進行仿真實驗后，驗證網(wǎng)絡(luò)延遲和網(wǎng)絡(luò)中的能量消耗的相互制約關(guān)系，可以根據(jù)用戶對網(wǎng)絡(luò)的需求，得到相應(yīng)的優(yōu)化路徑。

［1］ Cheng Chi－Tsun，Tse Chi K，Lau Francis C.M.A delay－aware data collection network structure for wireless sensor networks［J］.IEEE Sensors Journal，2011，11(3):699－710.

［2］ 顧洪軍，張 佐，吳秋峰.網(wǎng)絡(luò)控制系統(tǒng)中周期性通信的實時性充分條件［J］.測控技術(shù)，2001，20(6):1－4.

［3］ Heinzelman W，Chandrakasan A，Balakrishnan H.An applicationspecific protocol architecture for wireless micro sensor networks［J］.IEEE Translations on Wireless Communications，2002，1(4):660－670.

［4］ Lindsey S，Raghavendra C S.PEGASIS:Power－efficient gathering in sensor information systems［C］∥Proc IEEE Conf Aerosp Big Sky，MT，USA，2002:1125－1130.

［5］ Geem Z，Kim J，Loganathan G.A new heuristic optimization algorithm:Harmony search［J］.Simulation，2001，76(2):60－68.

［6］ Geem Z W，Lee K S，Park Y.Application of harmony search to vehicle routing［J］.American Journal of Applied Sciences，2005，2(12):1552－1557.

［7］ Geem Z W.Optimal cost design of water distribution networks using harmony search［J］.Engineering Optimization，2006，38(3):259－280.

［8］ Mohemmed A W，Sahoo N C，Geok T K.Solving shortest path problem using particle swarm optimization［J］.Applied Soft Computing，2008，8(4):1643－1653.