1、智能信息處理論文Revised on November 25, 2020蟻群算法在無線傳感器網絡中的應用綜述姓名：張夢寒導師：劉劍飛（河北工業大學信息工程學院，天津，300401）摘要:大量的具有無線通信和數據處理能力傳感器器件通過一定的協議構成自 組織網絡-無線傳感器網絡。這種網絡可以有效的進行傳感數據收集和傳輸。然 而由于無線傳感器網絡具有自身的特點比如：通信、存儲和處理能力較弱，有 限的能量等，使得關于無線傳感器網絡的路由研究成為熱點。本文中對該網絡 的特點以及路由算法要考慮的影響因素進行了分析，然后給出蟻群優化算法在 無線傳感器網絡路由中的應用。該路由方法易于實現、基于局部信息、將多種

2、 影響因素以信息素形式表現出來。該路由方法的自組織、動態和多路徑的特性 比較適合應用于無線傳感器網絡的路由。關鍵詞：無線傳感器網絡；蟻群算法；路由算法；信息素Abstract: With a large number of wireless communication and data processing capacity sensor device through the certain agreement constitute a self-organizing network - wireless sensor network. The network can be With effe

3、ctive for sensing data collection and transmission. However, due to the wireless sensor network has its own characteristics such as: communication, storage, and handling ability is weak, the limited energy, etc., make about wireless sensor network routing research become this paper the characteristi

4、cs of the network and the routing algorithm to consider the influence factors of the points .Analysis, then give the ant colony optimization algorithm in the application of wireless sensor network routing.Key words: Wireless sensor network;Ant colony algorithm ;Routing algorithm;pheromone中圖分類號:TP18文

5、獻標識碼:A1引言隨著微電子技術，計算技術和無線通信技術的進步，制造低功耗的傳感器 在技術上和成本上已經成為可能。傳感器具有信息采集、數據處理和無線通信 多種功能。通常傳感器探測它周圍的環境并生成電信號，并且處理這些信號使它們表現為傳感器監測的目標或發生事件的屬性。無線傳感器網絡(WirelessSensor Network)包含了很多傳感器節點，這些傳感器可以相互通信 或是與外部的基站通信。大量的傳感器可以保證精確探測一個很大的區域。通常傳感器節點有傳感器模塊、處理模塊、無線通信模塊和能量模塊。傳 感器模塊負責監測信息的采集和數據轉換；處理模塊負責傳感器的操作，存儲 和處理自身采集的數據以及

6、其他節點發來的數據；無線通信模塊負責與其他傳 感器節點進行無線通信，交換控制消息和首發采集數據；能量供應模塊為傳感 器節點提供所需的能量1為實現了減小能量消耗這個目標，一方面可以把已有的路由技術應用到無 線傳感器網絡中，另一方面也可以設計專門適用于該網絡的路由方法。例如： 數據收集方法，簇方法，給每個節點分配不同任務，以數據為中心的方法。根 據網絡的結構，路由協議一般可以分成扁平網絡和分層網絡。在扁平網絡中， 每個節點都有相同的功能，而在分層網絡中，局部的節點組成簇，簇頭節點可 以調整數據量的大小來達到節約能量的目的。基于位置的路由使用節點的位置 信息來中繼數據到目標區域。2無線傳感器網絡中路

7、由的影響因素節點部署傳感器節點部署因應用情況而定，它影響路由協議的性能。節點部署情況 分為確定部署和隨機部署兩種。在確定部署中，傳感器被按照要求放置，數據 經事先設計好的路徑傳輸。在隨機部署中，傳感器被隨機放置，整個網絡是是 一種對等方式的結構。如果整個網絡中的節點分布式處理困難，那么局部節點 優化成簇會是一個比較好的解決方法，它可以有效的使用能量保證網絡的連接。由于傳感器節點能量和帶寬的限制，它們之間通常只能在比較短的距離內 進行通信，因此一條路徑由多跳組成。（2）能量消耗在無線環境下，傳感器節點使用有限的能量進行計算和數據傳輸，因此要 為這些通信和計算保證能量，而節點使用時間取決于電池的壽

8、命。在多跳的無 線傳感器網絡中，每個節點既是數據發送者也是數據接收者，因為能量耗盡導 致節點失效會改變網絡的拓撲結構，從而改變路由情況，重新組織網絡路由 2（3）數據報告模型在無線傳感器網絡中，數據感知和報告取決于數據報告的應用和時間關鍵 度。數據報告可以分為時間驅動，事件驅動，查詢驅動以及混合型。時間驅動模型適用 于對周期性監測數據的應用。傳感器節點周期性的啟動傳感器和數據發送機制 以探測環境傳輸數據。在事件驅動和查詢驅動模型中，對于監控對象屬性值突 然發生劇烈變化或是基站發出的查詢，傳感器節點要立刻做出反應。這兩種模 型適用于對時間關鍵度十分敏感的應用。同時，這些 模型還可以結合起來運用。

9、（4）節點連接異構根據實際應用，一個傳感器節點可能會有不同的任務和功能，異構的傳感器節 點會引起一些技術上的問題，這些專用的傳感器可以單獨部署，或是多個功能 集成于一個傳感器節點。而在這些節點中也因為不同服務的要求，數據讀取和 報告的速率也不相同，這種差異也會帶來使用數據報告模型的不同。（5）容錯性一些傳感器節點因為能量耗盡，遭到破壞，或是環境的干擾失效，這些失 效不能影響整個網絡的正常運行。這時路由協議必須有機制重新建立路由。（6）網絡動態性許多網絡結構假設傳感器節點是靜態的，然而在有的應用中基站和節點有 時是需要移動的，移動節點發送和接收路由消息是一個具有挑戰性的課題，因 為此時路由穩定性

10、變得十分重要。3基于蟻群算法的路由蟻群算法是來源于對自然界螞蟻群行為的觀察和抽象。蟻群覓食時可以找 到蟻窩與食物間的最短路徑，這有賴于一種叫信息素的化學物質，螞蟻來往于 兩者之間，它們釋放信息素，為后來的螞蟻提供路徑向導4,5,6。7這樣的行為是 對現實情況很好的反應，這種思想也適用于無線傳感器網絡。（1）路由模型模型中設無線傳感器網絡拓撲結構為一張無向圖G（V,E），、表示傳感器 節點，V表示所有傳感器節點的集合，如果兩個節點可以七和七相互通信，則 兩者存在一條邊e，網絡中所有邊的集合表示為E。，（t）表示t時刻在邊e 上沉積的信息素的濃度。每個節點維護一張信息素表，記錄和它相連的邊上信 息

11、素的濃度。各邊信息素濃度更新按照以下公式進行：在t+1時刻，e上的信息素值等于蒸發后殘留信息素加上信息素增量之 和。P e Id,1 表示信息素蒸發系數，1-p表示殘留信息素系數，安G）表示ij信息素增量。e的信息素通過HELLO信息和回溯螞蟻（Backward Ant）進行更 新，信息增量厘G）使用以下公式計算：ijP是當前節點u的能量值，p .是V能量最大值，T是一跳的往返時間iimaxi）iij（Round Trip Time），N是V的當前連接數，如果一條確定的路由通過該節 點，則稱該節點有一個連接。Tmax和Nmax是往返時間和連接數的閾值，a，P是往返時間和連接數的系數，它們共同限

12、定信息素的值。該公式表明對于能 量比較多，往返時間短，連接數少的節點信息素的增量比較大。路由過程當源節點d希望與目的節點s通信，但是沒有關于d的路由信息，s必須尋找 一條從s到d的路徑。通常s廣播一個后應前行螞蟻（reactiveforwardant） FA（s,d），每FA（s,d）包含族群ID，代數，時間戳，源節點和目的 節點信息，以及一個空棧，時間戳和棧用于記錄前行路徑情況。第一代螞蟻作 為自己族群的蟻后，每個族群都有一個ID。當中間節點接收到一個FA（s, d ）時，它會將節點ID加入FA（s, d ）堆棧中，同 時查找路由表，找到信息素最高的下一跳。如果有幾個結果可選擇，則當前代 螞

13、蟻生成相應數量新一代螞蟻發送到這些節點。通過以上方法，螞蟻可以很快 擴散整個網絡，從不同路徑到達目的節點。這里有可能中間節點接收到同一族 群中的螞蟻，而且螞蟻代數年輕，這種情況叫路由循環，這種情況下，節點直 接丟棄螞蟻，另外，如果螞蟻前行時間或是跳數超過限制，節點也丟棄螞蟻。為了防止一些節點過度使用，使網絡資源得到充分使用，目的節點應當獲 得整條路徑的境況，以便按照標準選擇一條最佳的路徑。在這里，中間節點不 能對路由情況進行比較和決策，只有目的節點可以終止前進螞蟻的路由過程,并且可以發出回溯螞蟻來確定路徑。螞蟻到達目的節點后，目的節點獲取螞蟻 中路徑信息，并計算路徑信息素的值與其它螞蟻的路徑信

14、息素值進行比較。整 條路徑的信息素計算如下：Td整個路徑的往返時間，H d是路徑的跳數，T和H,是相應的閾值， a,b是調節因子，它們共同決定了路徑的信息素值。目的節點都有一個對應于源 節點的計數器，用于記錄時間和螞蟻的數量。計數器以第一只到達目的節點的 螞蟻到來之時進行計數，當數量或時間超過閾值，目的節點將停止接受來自該源 節點的螞蟻。目的節點通過比較各路徑上信息素的值，得出最優路徑，并且向 該路發送回溯螞蟻，按照路徑節點反向順序到達源節點，并更新經過連接的信 息素值。源節點接收到回溯螞蟻開始發送數據，如果在限定時間內沒有收到回 溯螞蟻，源節點將發送前行螞蟻，重新進行路由發現。(3)路由信息

15、的更新通過上述方法進行的路由一旦建立，源節點將向目的節點發送數據，但是 網絡的拓撲結構是變化的，因此各節點需要更新信息。傳感器節點以一定速率 發送前應螞蟻(proactive ant)來探測路徑。這種螞蟻像數據包一樣單播出去， 有兩個作用：一是證實路徑依然有效，另一個作用是更新源節點和目的節點的 信息素表。當該螞蟻到達路徑上的節點，它就收集上面的信息素的信息，當到 達目的節點后，就用這些信息更新它的信息素表。然后，目的節點就會發送回 溯螞蟻，它的任務是更新源節點的信息素表，這樣源節點可以按照新的信息素 表進行路由。無線傳感器網絡中每個節點需要知道它相鄰節點的信息，包括每一連接的 往返時間，可用

16、帶寬，以及信息素的值。為了能夠及時準確反映網絡狀況，需要發送HELLO消息探測與鄰居的連接狀況，更新路由信息。HELLO消息包括發送 節點ID,時間戳，以及可用帶寬。HELLO消息每隔一段時間（比如1秒）廣播一 遍。接收到這個消息的節點，用當前時間減去時間戳來計算RTT，然后檢查該消 息發送節點是否在鄰居表中，如果在就更新鄰居表中相應的值，如果不在就在 鄰居表中添加該節點信息。該節點再發送一個HELLO信息給發送節點以更新它的 鄰居表。以此方式，每個節點都會周期性的收到這樣的信息，及時了解鄰居節 點的情況。在網絡中，每個節點通過與鄰居交換HELLO信息更新來跟新信息，如果某個 連接失效，也能很

17、快的發現。一個節點可以通過收到鄰居節點的HELLO信息或發 送過來的包來證實鄰居節點的存在。節點通過鄰居間發送HELL O消息來更新路由 信息，因此也能很快的發現連接失效。如果鄰居節點在一定時間內沒有返回消 息，則可以簡單的把該節點從鄰居表和路由表中刪除。相應的，該失效節點兩 端的節點發送信息給源節點和目的節點，它們將從路由表刪除這條路徑。4結束語本文介紹了無線傳感器網絡概念和特點，分析以及設計網絡路由協議所面臨 的挑戰，給出了了基于蟻群優化算法的無線傳感器網絡由算法。該路由算法考 慮了網絡的特點，具有自組織性，動態性。信息素的計算方法考慮了能量，往 返時間，跳數等多種因素。因此比較適合無線傳

18、感器網絡的路由。最后，衷心感謝河北工業大學夏克文教授在百忙中審閱此論文，同時感謝 夏克文老師對本工作的指導。參考文獻Akyildiz, W. Su, Y. Sankarasubramaniam, and E. Cayirci,Asurvey on sensor networks,IEEE Communications Magazine,Volume: 40 Issue: 8, pp. 102-114, August 2002.A. Manjeshwar and D. P. Agarwal, TEEN: a routing protocol for enhanced efficiency in

19、wireless sensor networks, In 1stInternational Workshop on Parallel and Distributed Computing Issues in Wireless Networks and Mobile Computing, April 2001.F. Ye, A. Chen, S. Liu, L. Zhang, A scalable solution to minimum cost forwarding in large sensor networks, Proceedings of the tenth International Conference on Computer Communications and Networks (ICCCN), pp. 304309, 2001.R. Beckers, . Deneubourg, S. Goss, “Trails and u-turns in the selection of a path by the ant Lasius niger,” vol. 159, no. 4, pp. 397-415, 1992.A. Colomi, M. Dorigo, V. Maniezzo, “Distributed optimizati