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

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

0 引 言

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

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

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

1.1 路徑傳輸延遲［2］

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

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

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

無(wú)線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)的能耗通常由三部分組成:微控制器單元(MCU)、收發(fā)單元(TCR)、傳感器主板(SB)。每個(gè)部分都會(huì)有一定的能量消耗，所以，傳感器節(jié)點(diǎn)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 和聲搜索算法概述

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

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

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

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

2)初始化和聲記憶庫(kù)

隨機(jī)生成HMS 個(gè)和聲x1，x2，…，xHMS放入和聲記憶庫(kù)，和聲記憶庫(kù)形式如下

3)生成一個(gè)新的和聲

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

4)更新和聲記憶庫(kù)

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

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

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

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

3.1 路徑生成的編碼方式

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

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

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

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

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

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

圖1 網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)圖Fig 1 Structure diagram of network topology

表1 編碼表Tab 1 Encoding table

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

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

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

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

3.3 結(jié)果與分析

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

在Matlab 環(huán)境下，對(duì)100 個(gè)節(jié)點(diǎn)的網(wǎng)絡(luò)應(yīng)用和聲搜索算法進(jìn)行仿真實(shí)驗(yàn)，考慮傳感器相鄰節(jié)點(diǎn)距離R ＜30 m。對(duì)延遲和能量消耗兩個(gè)目標(biāo)所占權(quán)重值的不同，分析延遲和能耗對(duì)網(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 變化趨勢(shì)可以看出:在運(yùn)行約600 代后，基本可以得到穩(wěn)定的數(shù)據(jù)傳輸路徑。由記錄的數(shù)據(jù)可知，取α=0，β=1，即單獨(dú)考慮能耗影響因素，路徑產(chǎn)生的能耗為2 695.86 J，延遲為10.4 s;取α=1，β=0，即單獨(dú)考慮降低延遲，導(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ù)，當(dāng)優(yōu)先考慮能耗因素，延遲會(huì)相應(yīng)偏高，而優(yōu)先考慮延遲因素，則能耗相對(duì)較高，雖然都未達(dá)到單方面的最優(yōu)值，但綜合考慮能量消耗和網(wǎng)絡(luò)延遲兩方面因素，可以得到滿足總目標(biāo)的較優(yōu)傳輸路徑。由此可見(jiàn)，網(wǎng)絡(luò)延遲和網(wǎng)絡(luò)中的能量消耗兩方面因素相互制約，無(wú)法同時(shí)達(dá)到最優(yōu)狀態(tài)，而給延遲和能耗設(shè)定相應(yīng)的權(quán)重值，可以得到用戶所需求的相應(yīng)優(yōu)化路徑。

4 結(jié) 論

本文應(yīng)用和聲搜索算法解決無(wú)線傳感器網(wǎng)絡(luò)中低延遲和低能耗的雙目標(biāo)優(yōu)化問(wèn)題。分析了網(wǎng)絡(luò)中延遲和能耗模型，同時(shí)在找尋最優(yōu)路徑時(shí)，采用基于優(yōu)先級(jí)的路徑編碼算法，迭代更新和聲記憶庫(kù)。在Matlab 仿真環(huán)境下對(duì)網(wǎng)絡(luò)進(jìn)行仿真實(shí)驗(yàn)后，驗(yàn)證網(wǎng)絡(luò)延遲和網(wǎng)絡(luò)中的能量消耗的相互制約關(guān)系，可以根據(jù)用戶對(duì)網(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)中周期性通信的實(shí)時(shí)性充分條件［J］.測(cè)控技術(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.