基于ACS的無線傳感器網絡區分服務路由算法

趙宏，胡智，聞英友

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

1 引言

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

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

無線傳感器網絡中的感知數據傳輸，需要服務質量QoS保證，可以將其分為3個方面[3]。

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

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

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

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

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

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

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

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

傳統的路由算法是節點根據數據傳輸延遲、傳輸可靠性和能量開銷進行簡單加權優化處理，從而找出網絡內的最優路徑，但是，節點按照QoS要求傳輸數據是需要消耗網絡能量的，保證路由傳輸的延遲和可靠性，與網絡能量開銷之間并不是簡單的加權關系。節點通常具有一定的運算推理能力，可以利用在網絡中采集的網絡信息，進行決策尋找合適的路徑進行數據轉發，轉發數據的節點根據鄰居節點行為情況，選出最適合的鄰居節點完成數據傳輸。博弈論正是一種研究決策的理論，依靠參加活動主體的決策，相互作用后得到整個活動的資源優化配置。使用博弈論建立路由模型可以從局部的節點決策行為，權衡數據傳輸的收益和開銷，尋找到全局的最優路徑，實現整個網絡資源的合理利用。

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

2 相關工作

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

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

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

3 無線鏈路

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

圖1 分組成功接收率與距離的關系

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

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

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

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

圖2 提供區分QoS服務的鄰居節點

4 博弈路由模型

無線傳感器網絡節點都具有一定的計算推斷能力，可以通過自身采集到的網絡信息，決策路由中的下一跳節點。為了滿足服務質量要求，并實現全網優化，網絡節點通常考慮2個方面因素。

1) 盡可能選擇能夠提供最大 QoS收益的節點轉發數據到sink節點，這些數據包括節點自身感知到的數據以及節點轉發的數據。

2) 盡可能選擇后續跳數最少且能量最大的鄰居節點轉發數據，從而延長整個網絡和節點的生命期。避免從源節點到目的節點路徑上的關鍵節點由于頻繁轉發數據而能量耗盡，造成網絡分區，降低覆蓋率，縮短網絡使用的生命期。

整個網絡的路由過程是一個動態過程，每一個參與路由的節點權衡發送和轉發數據的收益和開銷，從網絡節點的個體預測行為和實際行為，來優化全網的資源。

4.1 網絡節點及行動順序

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

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

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

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

4.3 信息集和效用函數

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

1) 收益

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

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

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

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

2) 代價

節點在發送和轉發數據時，主要的能量開銷包括計算開銷和通信開銷，而計算開銷遠小于通信開銷[27]。通信開銷主要是由數據的長度和經過的跳數來確定。在考慮跳數和數據分組長度的情況下，發送和轉發數據的通信開銷可簡化為

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

3)效用(payoff)

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

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

證明 對于節點i的策略li，有

5 ADSGR算法設計與分析

本文的目標是為每一類 QoS數據尋找到最優的路由路徑，由于無線傳感器網絡的無線鏈路特點以及環境參數較多，會存在多個納什均衡路徑。通過無線鏈路對QoS提供區分服務，在博弈的效用基礎上，采用蟻群優化ACS，設計了基于ACS的區分服務路由算法。根據無線傳感器網絡的3種QoS分類，分別創建3類螞蟻，通過各類路徑上信息素和啟發因子計算下一跳節點，經過多次迭代找到最適合各類QoS數據的路由。

5.1 下一跳節點轉移函數

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

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

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

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

5.2 路徑信息素更新規則

1) 全局更新

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

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

2) 局部更新

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

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

5.3 算法步驟

步驟1 初始化，Nc=0，設置節點每條邊的信息素為常數。

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

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

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

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

步驟 6 迭代次數 Nc=Nc+1，如果 Nc小于設定迭代次數且不收斂，轉步驟2，否則，轉步驟7。

步驟 7 更新節點路由表的各類服務路徑，停止當前搜索周期，設定下一搜索周期定時器，當定時器到期時，轉步驟1。

5.4 算法分析

定理 2 ADSGR算法得到的路由路徑是最優路徑。

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

定理3 ADSGR算法不會產生回路。

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

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

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

其中，ρ為揮發系數，z為局部更新中最優路徑上的螞蟻數，選擇參數為q0，則網絡螞蟻的數量為

對式（21）兩邊取對數，可得，

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

6 實驗結果與分析

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

表1 ADSGR的主要參數

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

圖3 QoS-1數據傳輸延遲比較

圖3和圖4分別表示在傳輸QoS-1和QoS-3數據時的延遲。可以看出，在節點距離sink較近時3種算法的傳輸延遲基本相等，但是，隨著到sink節點距離的增大，MMSPEED和ADSGR在傳輸延遲上比 Dijkstra具有更小的傳輸延遲。ADSGR對于QoS-1數據傳輸的平均延遲是54.57 ms，約為Dijkstra的 85%，但稍大于 MMSPEED，這是由于 ADSGR選擇的轉發節點比MMSPEED的更接近當前節點，從而增加跳數，且延長時間。對于QoS-3數據傳輸，在分組丟失率小于 10%時，ADSGR平均延遲是55.97 ms，約為Dijkstra的88%，且小于MMSPEED。在有可靠性要求時，ADSGR和MMSPEED都選擇較為可靠的節點，即較近節點，經過優化后，ADSGR在傳輸QoS-3數據時，延遲性能更好。

圖4 QoS-3數據傳輸延遲比較

圖5 QoS-2數據傳輸分組丟失率比較

圖6 QoS-3數據傳輸分組丟失率比較

圖7 能量比較

圖8 QoS值比較

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

圖7顯示了在運行一段時間后節點剩余能量分布，ADSGR在能耗方面會選擇剩余能量較多，且跳數較少的節點轉發數據，再優化路由過程，因此，與Dijkstra和MMSPEED相比，網絡能耗更均衡。

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

7 結束語

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

[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] 文浩, 林闖, 任豐原等. 無線傳感器網絡的QoS體系結構[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] 孫巖, 馬華東, 劉亮. 一種基于蟻群優化的多媒體傳感器網絡服務感知路由算法[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] 崔艷榮, 李克清. 傳感器網絡中基于蟻群優化的數據查詢協議[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] 曹嘯, 王汝傳, 黃海平等. 無線多媒體傳感器網絡視頻流多路徑路由算法[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] 李慧芳, 姜勝明, 韋崗. 無線傳感器網絡中基于博弈論的路由建模[J]. 傳感器技術學報, 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] 曾加, 慕春棣. 基于不完全信息博弈的傳感器網絡能量平衡路由[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] 孫佩剛, 趙海, 羅玎玎等. 無線傳感器網絡鏈路通信質量測量研究[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] 楊綸標, 高英儀. 模糊數學原理與應用(第四版)[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.