基于ACS的無線傳感器網(wǎng)絡區(qū)分服務路由算法

趙宏，胡智，聞英友

(1. 東北大學 信息科學與工程學院，遼寧 沈陽 110819；2. 東北大學 軟件中心，遼寧 沈陽 110819)

1 引言

無線傳感器網(wǎng)絡主要由帶有感知功能的通信節(jié)點組成，節(jié)點通過自組織的網(wǎng)絡通信協(xié)議為用戶傳輸感知數(shù)據(jù)，將傳感技術(shù)、微機電技術(shù)和無線通信技術(shù)進行了綜合應用[1,2]。最近幾年，無線傳感器網(wǎng)絡由于在環(huán)境監(jiān)控、軍事國防、國家安全、搶險救災和工業(yè)控制等領(lǐng)域的應用前景，并且作為物聯(lián)網(wǎng)的重要基礎(chǔ)實施，可與云計算服務連接等多種使用方式，受到了來自學術(shù)界和產(chǎn)業(yè)界的廣泛關(guān)注。

隨著物聯(lián)網(wǎng)應用需求的不斷發(fā)展，一個無線傳感器網(wǎng)絡需要同時承載不同類型的感知數(shù)據(jù)，并且可以并發(fā)運行，不同類型的感知數(shù)據(jù)需按照不同服務質(zhì)量要求發(fā)送到收集節(jié)點sink。對于某一種物理環(huán)境的周期感知并發(fā)送到收集節(jié)點的數(shù)據(jù)，僅有延遲的要求。例如，精細農(nóng)業(yè)中，對土壤溫度的監(jiān)控，數(shù)據(jù)反映的是當前一定時間內(nèi)的環(huán)境值，在有效的時間范圍內(nèi)有效，又由于有較多的節(jié)點數(shù)量覆蓋，所以，這類數(shù)據(jù)只需要在滿足一個較低分組丟失率的條件下，短時間內(nèi)到達收集節(jié)點即可。而對于沒有固定收集周期的感知數(shù)據(jù)，如根據(jù)某一事件產(chǎn)生的數(shù)據(jù)，包括當感知數(shù)據(jù)值大于某一設(shè)定閾值時產(chǎn)生的異常事件數(shù)據(jù)，以及用戶根據(jù)現(xiàn)場情況下達的立即查詢請求驅(qū)動的用戶查詢數(shù)據(jù)，則需要保證在有效時延和分組丟失率(可靠性)下將數(shù)據(jù)傳輸?shù)绞占?jié)點，對于一些媒體型數(shù)據(jù)，如圖像，在定期采集后，需要在滿足一定可靠性的情況下將其發(fā)送到收集節(jié)點，還有許多感知應用，都要依據(jù)應用場景而確定QoS要求。

無線傳感器網(wǎng)絡中的感知數(shù)據(jù)傳輸，需要服務質(zhì)量QoS保證，可以將其分為3個方面[3]。

1) 傳輸延遲。從源節(jié)點(感知節(jié)點)到目的節(jié)點(收集節(jié)點)傳輸數(shù)據(jù)分組和分組所需的延遲。

2) 傳輸可靠性。目的節(jié)點成功接收到的數(shù)據(jù)分組，所占源節(jié)點的實際發(fā)送數(shù)據(jù)分組的比例，即分組成功接收率，可靠性也可以用分組丟失率來表示，分組丟失率越低，可靠性越高。

3)能量開銷。無線傳感器網(wǎng)絡是以數(shù)據(jù)為中心的網(wǎng)絡，能量開銷來自于數(shù)據(jù)的處理和傳輸，而數(shù)據(jù)傳輸主要的能量開銷。

由于無線傳感器網(wǎng)絡需要同時承載多個不同感知應用，這些感知應用的數(shù)據(jù)并不一定是同時傳輸，且在延遲、可靠性上也有不同的需求，因此，將多個感知應用產(chǎn)生的數(shù)據(jù)根據(jù)延遲、可靠性分為3類：QoS-1、QoS-2和QoS-3。

1) QoS-1。以要求傳輸延遲為主的感知數(shù)據(jù)，其分組丟失率只需滿足數(shù)據(jù)可用性要求就可以，如周期型感知溫度應用數(shù)據(jù)、濕度應用數(shù)據(jù)等。

2) QoS-2。以要求傳輸可靠性為主的感知數(shù)據(jù)，其延遲只需滿足數(shù)據(jù)可用性即可，如監(jiān)控拍照圖片應用數(shù)據(jù)，連續(xù)時間溫度監(jiān)控應用數(shù)據(jù)等。

3) QoS-3。對傳輸延遲和可靠性都有嚴格要求的應用，如具體環(huán)境信息的用戶查詢應用，異常數(shù)據(jù)報警應用。

這3類QoS都需要兼顧網(wǎng)絡能量開銷，延長網(wǎng)絡的整體使用時間。

傳統(tǒng)的路由算法是節(jié)點根據(jù)數(shù)據(jù)傳輸延遲、傳輸可靠性和能量開銷進行簡單加權(quán)優(yōu)化處理，從而找出網(wǎng)絡內(nèi)的最優(yōu)路徑，但是，節(jié)點按照QoS要求傳輸數(shù)據(jù)是需要消耗網(wǎng)絡能量的，保證路由傳輸?shù)难舆t和可靠性，與網(wǎng)絡能量開銷之間并不是簡單的加權(quán)關(guān)系。節(jié)點通常具有一定的運算推理能力，可以利用在網(wǎng)絡中采集的網(wǎng)絡信息，進行決策尋找合適的路徑進行數(shù)據(jù)轉(zhuǎn)發(fā)，轉(zhuǎn)發(fā)數(shù)據(jù)的節(jié)點根據(jù)鄰居節(jié)點行為情況，選出最適合的鄰居節(jié)點完成數(shù)據(jù)傳輸。博弈論正是一種研究決策的理論，依靠參加活動主體的決策，相互作用后得到整個活動的資源優(yōu)化配置。使用博弈論建立路由模型可以從局部的節(jié)點決策行為，權(quán)衡數(shù)據(jù)傳輸?shù)氖找婧烷_銷，尋找到全局的最優(yōu)路徑，實現(xiàn)整個網(wǎng)絡資源的合理利用。

本文根據(jù)無線傳感器網(wǎng)絡中數(shù)據(jù)傳輸?shù)难舆t、可靠性和能量消耗3個方面要求，將QoS分為3類，根據(jù)無線傳感器網(wǎng)絡的無線鏈路物理特點，提供區(qū)分的路由服務，分析了在保證延遲和可靠性要求下進行網(wǎng)絡傳輸與能量開銷的博弈關(guān)系，在此基礎(chǔ)上，設(shè)計了基于 ACS的無線傳感器網(wǎng)絡區(qū)分服務路由算法ADSGR(ant colony system based differentiated service and game-theory routing)。利用通信性能較好的鄰居節(jié)點傳輸高可靠性的數(shù)據(jù)，通信性能較差的鄰居節(jié)點傳輸高延遲的數(shù)據(jù)，根據(jù)QoS的分類將螞蟻分為3類，按照不同的QoS要求計算相應的啟發(fā)因子，通過路徑質(zhì)量選擇邏輯上距離收集節(jié)點較近的鄰居節(jié)點轉(zhuǎn)發(fā)數(shù)據(jù)，利用最大效用值更新路徑信息素，加快算法收斂，節(jié)省網(wǎng)絡能量開銷，找到相應的最優(yōu)路徑。

2 相關(guān)工作

蟻群優(yōu)化(ACO, ant colony optimization)方法[4～6]是 M.Dorigo提出的一種性能優(yōu)良的啟發(fā)式隨機優(yōu)化算法，采用正反饋機制實現(xiàn)分布式全局優(yōu)化，通過信息素不斷更新，最終收斂于最優(yōu)路徑上。ACO應用于多目標全局優(yōu)化和網(wǎng)絡路由的組合優(yōu)化求解等問題，采用分布式計算方式，且計算復雜度低，適合求解無線傳感器網(wǎng)絡的路由問題。文獻[7]提出了一種多QoS保障的路由算法ASAR，通過加權(quán)平均網(wǎng)絡QoS參數(shù)并設(shè)置相應權(quán)重因子，利用蟻群算法進行路由選擇。文獻[8]提出了一種能量均衡的數(shù)據(jù)查詢協(xié)議EBDQ，根據(jù)路徑上的能量消耗情況，對路由上信息素進行獎懲，使網(wǎng)絡的能量消耗分散到不同的路徑上，以平穩(wěn)的方式降低整個網(wǎng)絡能耗。文獻[9]提出了基于改進蟻群算法的多徑路由算法ACMRA，對重要性不同的視頻數(shù)據(jù)進行多徑選擇，提高網(wǎng)絡數(shù)據(jù)吞吐量和視頻傳輸性能。文獻[10]提出了一種基于分簇結(jié)構(gòu)的多 QoS保障路由協(xié)議AntSensNet，通過建立多QoS參數(shù)的數(shù)學模型，利用蟻群算法尋找使得目標函數(shù)值最大的路徑。文獻[11]提出了一個適用于無線傳感器網(wǎng)絡的新型路由協(xié)議，利用蟻群算法優(yōu)化路由，提供有效的多路數(shù)據(jù)發(fā)送機制，以便在節(jié)點失效的情況下獲得可靠的通信。以上算法在求解QoS路由的某些方面上提高了性能，但沒有分析延遲、可靠性和能量開銷在路由傳輸中的關(guān)系。

博弈論[12]是應用數(shù)學的一個分支，已成為經(jīng)濟學的主要分析工具之一，近年來也被廣泛應用于通信和計算機研究領(lǐng)域，尤其是在無線傳感器網(wǎng)絡領(lǐng)域[13]。文獻[14]將非合作博弈理論應用于傳感器節(jié)點傳輸信號的能量控制。文獻[15,16]以傳感器節(jié)點為中心，使用合作博弈對傳輸可靠度和網(wǎng)絡能耗進行優(yōu)化，在保證傳輸可靠度、數(shù)據(jù)融合條件下，避免節(jié)點能量被過度消耗導致網(wǎng)絡分區(qū)問題，延遲網(wǎng)絡使用時間。文獻[17]考慮了路徑可靠度、網(wǎng)絡能耗和生存時間3個因素，使用博弈論建立基于節(jié)點理性偏好的路由博弈模型，并分析了模型的均衡問題。文獻[18]提出了一種基于博弈論模型的能量平衡路由算法 GTEBR，引入仲裁和自信概率，將不完全信息的博弈轉(zhuǎn)換為完全但不完美的博弈，以解決能量不均衡問題。文獻[19]采用非合作博弈理論對網(wǎng)絡自私節(jié)點的能量保存和最大生命周期建模，在此基礎(chǔ)上建立分簇機制。這些算法并沒有使用博弈對延遲、可靠性和能量開銷進行分析，但建立相應的路由算法。

本文對數(shù)據(jù)傳輸中延遲、可靠性和能量開銷進行博弈分析，兼顧無線傳感器網(wǎng)絡的無線鏈路特點，綜合考慮這些因素，提出了基于蟻群優(yōu)化的區(qū)分服務路由算法ADSGR。

3 無線鏈路

無線傳感器網(wǎng)絡所工作的無線鏈路為 IEEE 802.15.4規(guī)范，無線鏈路的物理特點主要是不可靠性和非對稱性[20～22]。不可靠性表現(xiàn)在數(shù)據(jù)分組在經(jīng)過無線鏈路后，成功接收的概率隨通信距離的增大而減小，圖1顯示了分組成功接收率與距離的關(guān)系。當節(jié)點在通信性能較高距離內(nèi)，即“高效區(qū)”，分組成功接收率大于90%；在通信性能較差距離內(nèi)，稱為“空白區(qū)”，分組的成功接收率小于 10%；在兩者之間的區(qū)域稱為“過渡區(qū)”，分組成功接收率在20%到90%之間。例如，當A發(fā)送數(shù)據(jù)分組時，由于B在高效區(qū)內(nèi)，所以可接收到90%以上的數(shù)據(jù)分組；C的接收率比較低，將C向B移近時，C的接收率會升高，但仍然會有一定的波動性；由于D在空白區(qū)，接收率基本為0。

圖1 分組成功接收率與距離的關(guān)系

無線鏈路一般是雙向的，非對稱性表現(xiàn)在雙向鏈路上分組成功接收率的差值大于 25%以上，因此，非對稱鏈路主要發(fā)生在2個節(jié)點的通信距離在過渡區(qū)內(nèi)，受網(wǎng)絡不同區(qū)域場強、功率和噪聲等因素的影響。

根據(jù)無線鏈路的以上特點，一個節(jié)點可以統(tǒng)計一定時間內(nèi)與鄰居節(jié)點在雙向鏈路上的分組成功接收率來估計鏈路質(zhì)量，ETX[23]正是利用此方法，接收節(jié)點利用指數(shù)加權(quán)移動平均算法計算分組成功接收率，并將結(jié)果發(fā)送回發(fā)送節(jié)點，發(fā)送節(jié)點再計算出鏈路質(zhì)量，同時接收節(jié)點也使用這種方式計算鏈路質(zhì)量，分組成功接收率越大，鏈路質(zhì)量越好，ETX值越小。節(jié)點間的無線鏈路可以看成帶 ACK確認機制的雙向信道，節(jié)點i到鄰居節(jié)點的單跳鏈路ETX，可由正向和反向鏈路的分組成功接收率計算得到，設(shè)正向鏈路的分組成功接收率為df，反向鏈路的分組接收成功接收率為dr，則分組的成功接收和確認概率期望為df×dr，發(fā)送一個數(shù)據(jù)分組可看成Bernoulli實驗，因此，發(fā)送數(shù)據(jù)分組期望值為

令sink節(jié)點的ETX值為0，其他節(jié)點到Sink節(jié)點的路徑ETX為單跳鏈路ETXlink的累加和，即ETXpath

由于無線傳感器網(wǎng)絡物理鏈路的固有特點，并且ETX值可以綜合地反映無線鏈路質(zhì)量，在CTP協(xié)議中已成功應用[24]，可取最近傳輸數(shù)據(jù)的時間段為參數(shù)，將分組成功接收率在 75%～90%區(qū)域和90%～100%區(qū)域的鄰居節(jié)點轉(zhuǎn)換為相應的 ETXlink值，使用較大 ETXlink區(qū)域內(nèi)鄰居節(jié)點傳輸 QoS-1的數(shù)據(jù)，使用較小 ETXlink區(qū)域內(nèi)鄰居節(jié)點傳輸QoS-2和QoS-3的數(shù)據(jù)，如圖2所示，以區(qū)分提供不同QoS類別服務的節(jié)點。

圖2 提供區(qū)分QoS服務的鄰居節(jié)點

4 博弈路由模型

無線傳感器網(wǎng)絡節(jié)點都具有一定的計算推斷能力，可以通過自身采集到的網(wǎng)絡信息，決策路由中的下一跳節(jié)點。為了滿足服務質(zhì)量要求，并實現(xiàn)全網(wǎng)優(yōu)化，網(wǎng)絡節(jié)點通?？紤]2個方面因素。

1) 盡可能選擇能夠提供最大 QoS收益的節(jié)點轉(zhuǎn)發(fā)數(shù)據(jù)到sink節(jié)點，這些數(shù)據(jù)包括節(jié)點自身感知到的數(shù)據(jù)以及節(jié)點轉(zhuǎn)發(fā)的數(shù)據(jù)。

2) 盡可能選擇后續(xù)跳數(shù)最少且能量最大的鄰居節(jié)點轉(zhuǎn)發(fā)數(shù)據(jù)，從而延長整個網(wǎng)絡和節(jié)點的生命期。避免從源節(jié)點到目的節(jié)點路徑上的關(guān)鍵節(jié)點由于頻繁轉(zhuǎn)發(fā)數(shù)據(jù)而能量耗盡，造成網(wǎng)絡分區(qū)，降低覆蓋率，縮短網(wǎng)絡使用的生命期。

整個網(wǎng)絡的路由過程是一個動態(tài)過程，每一個參與路由的節(jié)點權(quán)衡發(fā)送和轉(zhuǎn)發(fā)數(shù)據(jù)的收益和開銷，從網(wǎng)絡節(jié)點的個體預測行為和實際行為，來優(yōu)化全網(wǎng)的資源。

4.1 網(wǎng)絡節(jié)點及行動順序

網(wǎng)絡節(jié)點是整個博弈路由建立過程中的參與者，是網(wǎng)絡中可以正常工作的傳感器節(jié)點，可以產(chǎn)生數(shù)據(jù)，也可以轉(zhuǎn)發(fā)數(shù)據(jù)的節(jié)點。首先，源節(jié)點產(chǎn)生感知數(shù)據(jù)，發(fā)起路由行動，源節(jié)點選擇一個較為合適的鄰居節(jié)點進行轉(zhuǎn)發(fā)，鄰居節(jié)點收到消息后采取相應的行動再進行轉(zhuǎn)發(fā)，一直持續(xù)到下一跳鄰居節(jié)點為sink節(jié)點時停止。

4.2 行動策略空間與意外事件

節(jié)點參與傳遞數(shù)據(jù)并向一個鄰居節(jié)點轉(zhuǎn)發(fā)路由請求。參與者節(jié)點 i的策略集 Li=(li,1, …，li,i-1,li,i+1,…,li,s)，li,j∈{0,1}，li,j=1 表示節(jié)點 i選擇節(jié)點j作為下一跳節(jié)點，而li,j=0表示節(jié)點i未選擇節(jié)點j作為下一跳節(jié)點。通常情況下，節(jié)點僅轉(zhuǎn)發(fā)數(shù)據(jù)分組到一個節(jié)點，可以將這種策略空間限制到純策略，則向量Li中最多只有一個值為1，其余都為0。將節(jié)點i的上一跳節(jié)點從策略集中刪除，再將不符合通信質(zhì)量要求鄰居節(jié)點從策略集中刪除，根據(jù)鏈路質(zhì)量將剩下鄰居節(jié)點分為對應QoS-1的鄰居節(jié)點集以及對應 QoS-2和 QoS-3的鄰居節(jié)點集其中，m表示節(jié)點i在滿足QoS-1的鏈路質(zhì)量時的鄰居節(jié)點個數(shù)，n表示節(jié)點i在滿足QoS-2和QoS-3的鏈路質(zhì)量時的鄰居節(jié)點個數(shù)。由于每個節(jié)點的鄰居節(jié)點個數(shù)都是有限的，因此，純策略空間的博弈中參與者節(jié)點的策略空間也是有限的。

由于無線傳感器網(wǎng)絡節(jié)點資源嚴重受限，通信和運行表現(xiàn)為易失敗性，設(shè)節(jié)點i失敗概率為1-pi，根據(jù)鏈路質(zhì)量選擇鄰居節(jié)點，因此，節(jié)點 iQoS-1的失敗率1-pi為[0,0.2)的均勻分布，節(jié)點iQoS-2,3的失敗率1-pi為[0,0.1)的均勻分布。

4.3 信息集和效用函數(shù)

路由參與節(jié)點的每個行動都會為網(wǎng)絡的數(shù)據(jù)傳輸帶來一定的效用，可由效用支付函數(shù)表示，包括收益(benefit)和代價(cost)。由于博弈中參與節(jié)點的策略和行動都是相互依賴的，因此每個參與節(jié)點的效用都與其他參與節(jié)點策略有關(guān)。路由的過程是選擇下一跳節(jié)點的過程，下一跳鄰居的信息集對于當前的策略選擇非常重要，收益和代價的計算主要是根據(jù)鄰居節(jié)點的信息集。信息集主要包括對所轉(zhuǎn)數(shù)據(jù)經(jīng)過該節(jié)點到達sink節(jié)點所需的時間、可靠率、能量信息和跳數(shù)信息，再基于這些信息計算收益和代價，從而得到路由效用值。效用值越大，說明該鄰居節(jié)點越應被選為下一跳節(jié)點，即該策略越好。

1) 收益

節(jié)點在發(fā)送和轉(zhuǎn)發(fā)數(shù)據(jù)時，根據(jù)每一個鄰居節(jié)點到sink節(jié)點的延遲、可靠率和能量計算在該條路由路徑上的收益。無線傳感器網(wǎng)絡協(xié)議是一種自組織網(wǎng)絡協(xié)議，并且無線鏈路并不總是穩(wěn)定的，這使得數(shù)據(jù)在路由的過程中會出現(xiàn)波動，甚至丟失，很難給出精確的測量，可以采用模糊隸屬度的方法給出每條路徑的評價值[25,26]，對節(jié)點在延遲、分組丟失率和能量上的評價為

其中，DH是最大傳輸延遲，LH是最大分組丟失率，dj與lj分別為節(jié)點j提供的延遲和分組丟失率。與分別為節(jié)點j的剩余能量與初始能量。因此，在網(wǎng)絡傳輸過程中，通過節(jié)點j發(fā)送或轉(zhuǎn)發(fā)數(shù)據(jù)的綜合評價值為

其中，αD、αL和 αE分別為反映延遲、可靠率和能量相對重要程度的權(quán)重系數(shù)，其和為1。對于QoS-1數(shù)據(jù)，αD+αE=1，αL=0；對于 QoS-2 數(shù)據(jù)，αD=0，αL+αE=1；對于 QoS-3 數(shù)據(jù)，αD+αL+αE=1。因此，0≤≤1，其值越大，該鄰居節(jié)點的綜合評價值越高。因此，節(jié)點的綜合收益值就是選擇所有后續(xù)路由節(jié)點的綜合評價值的平均。

其中，L(P)是路徑P的長度，pk是未發(fā)生意外事件的概率，sink節(jié)點的值為1。

2) 代價

節(jié)點在發(fā)送和轉(zhuǎn)發(fā)數(shù)據(jù)時，主要的能量開銷包括計算開銷和通信開銷，而計算開銷遠小于通信開銷[27]。通信開銷主要是由數(shù)據(jù)的長度和經(jīng)過的跳數(shù)來確定。在考慮跳數(shù)和數(shù)據(jù)分組長度的情況下，發(fā)送和轉(zhuǎn)發(fā)數(shù)據(jù)的通信開銷可簡化為

其中，Erx和Etx分別為發(fā)送和接收1bit數(shù)據(jù)的能量消耗，k為數(shù)據(jù)消息長度，P是路由路徑，L(P)是路徑P長度，即跳數(shù)。考慮路由路徑上的通信開銷并不能反映出路徑上節(jié)點的代價。當路徑上節(jié)點的能量較大，且路徑較短時，路由通信代價較小，從而容易被選為下一跳節(jié)點。通過路徑長度和網(wǎng)絡直徑的比值，以及它與路由節(jié)點的剩余能量率，可以計算代價為

3)效用(payoff)

整個的路由過程，就是網(wǎng)絡中參與路由節(jié)點的博弈過程。令 l=(li,l-i)是路由博弈中任一組策略組合，其中，li表示參與節(jié)點i的策略，l-i=(l1, li-1, li+1,…,ln)表示其他參與節(jié)點的策略。該策略組合下參與節(jié)點i的效用函數(shù)用表示，包括節(jié)點i的收益和代價兩部分。節(jié)點i的和都與所有參與節(jié)點的策略有關(guān)，路由博弈中節(jié)點的策略和行動是相互影響的。只有參與傳遞數(shù)據(jù)任務的節(jié)點才需要考慮數(shù)據(jù)在傳輸過程的收益和代價的權(quán)衡，而對于那些沒有參與傳遞數(shù)據(jù)任務的節(jié)點，不需要付出能量代價和考慮QoS收益，所以，效用值可以為零，其效用為

定理1 源節(jié)點到sink節(jié)點的納什均衡路由路徑存在。

證明 對于節(jié)點i的策略li，有

5 ADSGR算法設(shè)計與分析

本文的目標是為每一類 QoS數(shù)據(jù)尋找到最優(yōu)的路由路徑，由于無線傳感器網(wǎng)絡的無線鏈路特點以及環(huán)境參數(shù)較多，會存在多個納什均衡路徑。通過無線鏈路對QoS提供區(qū)分服務，在博弈的效用基礎(chǔ)上，采用蟻群優(yōu)化ACS，設(shè)計了基于ACS的區(qū)分服務路由算法。根據(jù)無線傳感器網(wǎng)絡的3種QoS分類，分別創(chuàng)建3類螞蟻，通過各類路徑上信息素和啟發(fā)因子計算下一跳節(jié)點，經(jīng)過多次迭代找到最適合各類QoS數(shù)據(jù)的路由。

5.1 下一跳節(jié)點轉(zhuǎn)移函數(shù)

定義 1 路由梯度方向，通過鏈路質(zhì)量的累加值 ETXpath反映當前節(jié)點到sink節(jié)點的邏輯距離，ETXpath越小，說明節(jié)點離sink節(jié)點越近，越應該選擇這樣的節(jié)點進行路由，用Direct(j)表示。

如果當前節(jié)點為 i，下一跳鄰居節(jié)點為 j，則Direct(j)為

根據(jù)鄰居節(jié)點選擇博弈過程的效用函數(shù)和路由梯度方向，使用 tabu表記錄螞蟻所路由過的節(jié)點，則第t類服務的螞蟻k從節(jié)點i轉(zhuǎn)移到鄰居節(jié)點j的轉(zhuǎn)移概率函數(shù)如下式

其中，q0是選擇參數(shù)(0≤q0≤1)；表示在路徑(i,j)上的第t類服務的信息素；為相應的QoS類服務的啟發(fā)因子，是節(jié)點i在路由選擇博弈時的效用函數(shù)；參數(shù)α、β可反映路由選擇中路徑上殘留信息素和啟發(fā)因子的重要程度，α越大，螞蟻選擇其他螞蟻走過的路徑可能性就越大，表明螞蟻協(xié)作性越強，β越大，螞蟻受效用函數(shù)對下一跳影響就越大。

5.2 路徑信息素更新規(guī)則

1) 全局更新

在m只螞蟻成功地完成一次路由尋徑后，根據(jù)博弈的效用值，選出最大效用值的路由：

其中，ρG∈(0,1)是揮發(fā)系數(shù)，防止鏈路上信息素的無限增長；t表示QoS類別；表示在路由尋徑搜索中節(jié)點i到節(jié)點j上t類信息素的增量；P是對應的路徑，L(P)是路徑的長度；Q是調(diào)整系數(shù)。

2) 局部更新

當螞蟻經(jīng)過相鄰節(jié)點i和j時，需對所經(jīng)過的邊進行信息素更新。

其中，Lρ∈(0,1)是一個參數(shù)，QoStijτ-Δ 可以取0。

5.3 算法步驟

步驟1 初始化，Nc=0，設(shè)置節(jié)點每條邊的信息素為常數(shù)。

步驟2 針對不同QoS類路由請求，構(gòu)造相應的m只尋徑螞蟻，每只螞蟻根據(jù)式(15)，在相應的QoS類的鄰居節(jié)點中選擇下一跳路由節(jié)點，并將當前節(jié)點加入到tabu表中。

步驟3 利用QoS類的螞蟻k進行路由尋徑，對于經(jīng)過的路徑邊，根據(jù)式(20)進行局部更新。

步驟4 累加螞蟻k路由路徑中的節(jié)點效用值，計算出路徑的效用值，根據(jù)式(17)尋找出最大效益值。

步驟5 在本次路由尋徑迭代后，根據(jù)式(18)，對最大效用值的路徑進行全局更新，按照tabu表中路徑節(jié)點的記錄順序，反向更新相應邊上的信息素。

步驟 6 迭代次數(shù) Nc=Nc+1，如果 Nc小于設(shè)定迭代次數(shù)且不收斂，轉(zhuǎn)步驟2，否則，轉(zhuǎn)步驟7。

步驟 7 更新節(jié)點路由表的各類服務路徑，停止當前搜索周期，設(shè)定下一搜索周期定時器，當定時器到期時，轉(zhuǎn)步驟1。

5.4 算法分析

定理 2 ADSGR算法得到的路由路徑是最優(yōu)路徑。

證明 算法在更新時總是選擇效用值最大的路徑進行全局更新，從而增加了路徑上信息素濃度，這樣每次循環(huán)中效用最大的路徑上總是可以累加到更多的信息素，經(jīng)過多次迭代后，在效用值大的路徑上的信息素濃度也會最大，所以，算法得到的路由路徑收斂于最優(yōu)路徑。

定理3 ADSGR算法不會產(chǎn)生回路。

證明 由于路由梯度方向的指引，Direct( j)=1，節(jié)點i在選擇鄰居節(jié)點j轉(zhuǎn)發(fā)數(shù)據(jù)時，總是選擇比自己 ETXpath小的節(jié)點轉(zhuǎn)發(fā)，即也就是說節(jié)點j比節(jié)點i在通信距離上更加接近sink節(jié)點，同樣，節(jié)點j在選擇鄰居節(jié)點k轉(zhuǎn)發(fā)數(shù)據(jù)時，也采取這種方法，所以，每一跳節(jié)點在選擇轉(zhuǎn)發(fā)節(jié)點時，都選擇比自己距離sink更近的節(jié)點，從而不會返回到之前距離sink節(jié)點較遠的上流節(jié)點，避免了回路的產(chǎn)生。

定理4 路由報文開銷復雜度為 O （ N c ? n?logn） 。

證明 設(shè) τ0是初始信息素值，φ1(n)為更新的效用值最大路徑上的平均信息素值的增長系數(shù)，φ2(n)為全局更新后的效用值最大路徑上的平均信息素值的增長系數(shù)，根據(jù)蟻群算法計算過程，可得到

其中，ρ為揮發(fā)系數(shù)，z為局部更新中最優(yōu)路徑上的螞蟻數(shù)，選擇參數(shù)為q0，則網(wǎng)絡螞蟻的數(shù)量為

對式（21）兩邊取對數(shù)，可得，

而路由的跳數(shù)h(n)又受網(wǎng)絡規(guī)模n的限制，通常小于n，是n的一個子集，所以，m×h(n)是網(wǎng)絡路由報文的數(shù)量級，復雜度為 O （ Nc ? n?log n） 。

6 實驗結(jié)果與分析

本文以 TOSSIM[28]作為網(wǎng)絡模擬環(huán)境，使用Java語言隨機生成網(wǎng)絡拓撲，對ADSGR進行了仿真實驗。在100 m×100 m的區(qū)域內(nèi)隨機地部署100個節(jié)點，組成一個無線傳感器網(wǎng)絡。采用均勻分布的方式隨機部署網(wǎng)絡節(jié)點，約每20 m×20 m范圍內(nèi)部署2～6個節(jié)點，節(jié)點間隔距離不小于7 m。數(shù)據(jù)分組長度為100 byte，通信半徑約40 m，迭代次數(shù)Nc為35。ADSGR的主要參數(shù)設(shè)置如表1所示。

表1 ADSGR的主要參數(shù)

隨機選取區(qū)域邊緣的某一處節(jié)點為sink節(jié)點，在整個區(qū)域內(nèi)隨機選取30個節(jié)點作為感知數(shù)據(jù)源，以它們到sink節(jié)點的距離進行編號。再進行大量數(shù)據(jù)發(fā)送實驗，并將ADSGR與Dijkstra和MMSPEED[29]進行比較，實驗結(jié)果如圖3～圖8所示。

圖3 QoS-1數(shù)據(jù)傳輸延遲比較

圖3和圖4分別表示在傳輸QoS-1和QoS-3數(shù)據(jù)時的延遲?？梢钥闯?，在節(jié)點距離sink較近時3種算法的傳輸延遲基本相等，但是，隨著到sink節(jié)點距離的增大，MMSPEED和ADSGR在傳輸延遲上比 Dijkstra具有更小的傳輸延遲。ADSGR對于QoS-1數(shù)據(jù)傳輸?shù)钠骄舆t是54.57 ms，約為Dijkstra的 85%，但稍大于 MMSPEED，這是由于 ADSGR選擇的轉(zhuǎn)發(fā)節(jié)點比MMSPEED的更接近當前節(jié)點，從而增加跳數(shù)，且延長時間。對于QoS-3數(shù)據(jù)傳輸，在分組丟失率小于 10%時，ADSGR平均延遲是55.97 ms，約為Dijkstra的88%，且小于MMSPEED。在有可靠性要求時，ADSGR和MMSPEED都選擇較為可靠的節(jié)點，即較近節(jié)點，經(jīng)過優(yōu)化后，ADSGR在傳輸QoS-3數(shù)據(jù)時，延遲性能更好。

圖4 QoS-3數(shù)據(jù)傳輸延遲比較

圖5 QoS-2數(shù)據(jù)傳輸分組丟失率比較

圖6 QoS-3數(shù)據(jù)傳輸分組丟失率比較

圖7 能量比較

圖8 QoS值比較

圖5和圖6分別表示在傳輸QoS-2和QoS-3數(shù)據(jù)時的分組丟失率。與延遲類似，隨著到sink節(jié)點距離的增大，MMSPEED和ADSGR在分組丟失率上比Dijkstra具有更小值，但是，在節(jié)點距離sink較近時，3種算法的分組丟失率也基本相等。由于距離增加，跳數(shù)也增加，多次轉(zhuǎn)發(fā)后分組丟失率也相應地增加了。ADSGR對于QoS-2數(shù)據(jù)傳輸分組丟失率約為0.023 6，明顯低于Dijkstra，在選擇鄰居節(jié)點轉(zhuǎn)發(fā)時，ADSGR和MMSPEED都選擇較近節(jié)點轉(zhuǎn)發(fā)，經(jīng)過優(yōu)化后，ADSGR分組丟失率略小于MMSPEED。對于QoS-3數(shù)據(jù)傳輸，ADSGR在滿足數(shù)據(jù)傳輸延遲小于 200 ms的情況下，約為0.027 4，也低于Dijkstra和MMSPEED。在同時考慮延遲和分組丟失率的情況下，ADSGR可以選擇綜合值最好的節(jié)點轉(zhuǎn)發(fā)數(shù)據(jù)，從而得到更低分組丟失率，保證了數(shù)據(jù)傳輸?shù)目煽啃浴?/p>

圖7顯示了在運行一段時間后節(jié)點剩余能量分布，ADSGR在能耗方面會選擇剩余能量較多，且跳數(shù)較少的節(jié)點轉(zhuǎn)發(fā)數(shù)據(jù)，再優(yōu)化路由過程，因此，與Dijkstra和MMSPEED相比，網(wǎng)絡能耗更均衡。

圖8為感知區(qū)域節(jié)點的平均QoS值，從中可看出，ADSGR在感知區(qū)域內(nèi)的節(jié)點平均QoS值都高于Dijkstra和MMSPEED。通過以上實驗比較可以看出，ADSGR在延遲、可靠性、能耗和QoS值上具有更好的性能。

7 結(jié)束語

本文將無線傳感器網(wǎng)絡的QoS按照延遲、可靠性和能量開銷進行綜合分類，根據(jù)無線鏈路的特點提供對不同QoS要求的區(qū)分服務。分析了延遲，可靠性與傳輸中的網(wǎng)絡能耗之間的博弈關(guān)系，基于ACS設(shè)計了區(qū)分服務路由算法ADSGR，依據(jù)不同QoS要求選擇合適的路由，提高網(wǎng)絡的整體性能和資源利用率。與現(xiàn)有算法相比，該算法在數(shù)據(jù)傳輸?shù)难舆t、可靠性和能量開銷上表現(xiàn)較好。下一步工作是將該算法部署到實際的傳感器節(jié)點，如MicaZ、Telosb和Imote2等，并對數(shù)據(jù)融合和擁塞控制進行研究。

[1] AKYILDIZ I F, SU W, SANKARASUBRAMANIAM Y. Wireless sensor networks： a survey[J]. Computer Networks, 2002, 38(4)：393-422.

[2] YICK J, MUKHERJEE B, GHOSAL D. Wireless sensor networks survey [J]. Computer Networks, 2008, 52(2)： 2292-2330.

[3] 文浩, 林闖, 任豐原等. 無線傳感器網(wǎng)絡的QoS體系結(jié)構(gòu)[J]. 計算機學報, 2009, 32(3)：432-440.WEN H, LIN C, REN F Y, et al. QoS architecture in wireless sensor network[J]. Chinese Journal of Computer, 2009, 32(3)：432-440.

[4] DORIGO M, CARO G D. Ant algorithms for discrete optimization[J].Artificial Life, 1999, 5(3)：137-172.

[5] DORIGO M, GAMBARDELLA L M. Ant colony system： a cooperative learning approach to the traveling salesman problem[J]. IEEE Trans on Evolutionary Computation, 1997, 1(1)：53-66.

[6] DORIGO M, MANIEZZO V, COLOM I A. Ant system： optimization by a colony of cooperating agents[J]. IEEE Trans on Systems, Man,and Cybernetics： Part B, 1996, 26(1)：29-41.

[7] 孫巖, 馬華東, 劉亮. 一種基于蟻群優(yōu)化的多媒體傳感器網(wǎng)絡服務感知路由算法[J]. 電子學報, 2007, 35(4)：705-711.SUN Y, MA HD, LIU L. An ant-colony optimization based service aware routing algorithm for multimedia sensor networks[J]. Chinese Journal of Electronics, 2007,35(4)：705-711.

[8] 崔艷榮, 李克清. 傳感器網(wǎng)絡中基于蟻群優(yōu)化的數(shù)據(jù)查詢協(xié)議[J].軟件學報, 2010, 21(4)：793-801.CUI Y R, LI K Q. Data query protocol based on ant colony optimization for wireless sensor networks[J]. Chinese Journal of Software,2010, 21(4)：793-801.

[9] 曹嘯, 王汝傳, 黃海平等. 無線多媒體傳感器網(wǎng)絡視頻流多路徑路由算法[J]. 軟件學報, 2012, 23(1)：108-121.CAO X, WANG R C, HUANG H P, et al. Multi-path routing algorithm for video stream in wireless multimedia sensor networks[J].Chinese Journal of Software, 2012, 23(1)：108-121.

[10] COBO L, QUINTERO A, PIERRE S. Ant-based routing for wireless multimedia sensor networks using multiple QoS metrics[J]. Computer Networks, 2010, 54(17)：2991-3010.

[11] OKDEM S, KARABOGA D. Routing in wireless sensor networks using ant colony optimization[A]. Proceedings of the First NASA/ESA Conference on Adaptive Hardware and Systems[C].IEEE Press,2006.401-404.

[12] FUDENBERG D, TIROLE J. Game Theory [M]. MIT Press, 1991.

[13] MACHADO R, TEKINAY S. A survey of game-theoretic approaches in wireless sensor networks[J]. Computer Networks, 2008, 52(8)：3047-3061.

[14] SENGUPTA S, CHATTERJEE M, KWIAT K. A. A game theoretic framework for power control in wireless sensor networks[J]. IEEE Trans on computers, 2010, 59(2)：231-242.

[15] KANNAN R, SITHARAMA I S. Game-theoretic models for reliable path-length and energy-constrained routing with data aggregation in wireless sensor networks[J]. IEEE Journal on Selected Areas in Communication, 2004, 22(6)：1141-1150.

[16] KANNAN R, SARANGI S, IYENGAR S S, RAY L. Sensor-centric quality of routing in sensor networks[A]. Proceedings of IEEE Infocom[C]. San Francisco, CA, 2003. 692-701.

[17] 李慧芳, 姜勝明, 韋崗. 無線傳感器網(wǎng)絡中基于博弈論的路由建模[J]. 傳感器技術(shù)學報, 2007, 20(9)：2075-2079.LI H F, JIAN S M. Game-theoretic modeling on routing in wireless sensor networks[J]. Chinese Journal of Sensors and Actuators, 2007,20(9)：2075-2079.

[18] 曾加, 慕春棣. 基于不完全信息博弈的傳感器網(wǎng)絡能量平衡路由[J]. 自動化學報, 2008, 34(3)： 317-322.ZENG J, MU C D. Game theory-based energy balance routing with incomplete information in wireless sensor networks[J]. ACTA Automatica Sinica, 2008. 34(3)： 317-322.

[19] Koltsidas G, Pavlidou F N. A game theoretical approach to clustering of ad-hoc and sensor networks[J]. Telecommunication Systems, 2011,47： 81-93.

[20] 孫佩剛, 趙海, 羅玎玎等. 無線傳感器網(wǎng)絡鏈路通信質(zhì)量測量研究[J]. 通信學報, 2007, 28(10)： 14-22.SUN P G, ZHAO H, LUO D D, et al. Study on measurement of link communication quality in wireless sensor networks[J]. Journal on Communication, 2007, 28(10)： 14-22.

[21] SRINIVASAN K, KAZANDJIEVA M A, AGARWAL S, et al. The β-factor： measuring wireless link burstiness[A]. Proceedings of the 6th ACM Conference on Embedded network sensor system(SenSys)[C].Raleigh, NC, USA, 2008, 29-42.

[22] ZUNIGA M, KRISHNAMACHARI B. Analyzing the transitional region in low power wireless links[A]. Proceedings of IEEE SECON[C]. 2004. 517-526.

[23] DE COUTO D S J, AGUAYO D, BICKET J C, et al. A high-throughput path metric for multi-hop wireless routing[J]. Wireless Networks, 2005, 11(4)： 419-434.

[24] OMPRAKASH G, RODRIGO F, KYLE J, et al. Collection tree protocol[A]. Proceedings of the 7th ACM conference on Embedded network sensor system(SenSys)[C]. Berkeley, CA, USA, 2009.1-14.

[25] 王興偉, 秦佩玉, 郭磊等. 基于混合人工魚群的 ABC支持型切換決策機制[J]. 通信學報, 2010, 31(12)： 72-81.WANG X W, QIN P Y, GUO L, et al. Hybrid artificial fish swarm based handover decision scheme with ABC supported[J]. Journal on Communication, 2010, 31(12)： 72-81.

[26] 楊綸標, 高英儀. 模糊數(shù)學原理與應用(第四版)[M]. 廣州： 華南理工大學出版社, 2006. 41-49.YANG L B, GAO Y Y. Fuzzy Mathematics and Application (fourth edition)[M]. Guangzhou： South China University of Technology Press,2006, 41-49.

[27] BUETTNER M, YEE G, ANDERSON E, et al. X-MAC： a short preamble MAC protocol for duty-cycled wireless sensor networks[A].Proceedings of the 4th ACM conference on Embedded network sensor system(SenSys)[C]. New York, USA, 2006, 307-320.

[28] LEVIS P, LEE N, WELSH M, et al. TOSSIM： accurate and scalable simulation of entire tinyOS application[A]. Proceedings of the 1st ACM conference on Embedded network sensor system(SenSys)[C].Los Angeles, CA, USA, 2003, 126-137.

[29] FELEMBAN E, LEE C G, EKICI E. MMSPEED： multipath multi-SPEED protocol for QoS guarantee of reliability and timeliness in wireless sensor networks[J]. IEEE Trans on Mobile Computing,2006, 5(6)：738-754.