智能信息處理論文

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

2、 影響因素以信息素形式表現(xiàn)出來。該路由方法的自組織、動態(tài)和多路徑的特性 比較適合應(yīng)用于無線傳感器網(wǎng)絡(luò)的路由。關(guān)鍵詞：無線傳感器網(wǎng)絡(luò)；蟻群算法；路由算法；信息素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、獻標(biāo)識碼:A1引言隨著微電子技術(shù)，計算技術(shù)和無線通信技術(shù)的進步，制造低功耗的傳感器 在技術(shù)上和成本上已經(jīng)成為可能。傳感器具有信息采集、數(shù)據(jù)處理和無線通信 多種功能。通常傳感器探測它周圍的環(huán)境并生成電信號，并且處理這些信號使它們表現(xiàn)為傳感器監(jiān)測的目標(biāo)或發(fā)生事件的屬性。無線傳感器網(wǎng)絡(luò)(WirelessSensor Network)包含了很多傳感器節(jié)點，這些傳感器可以相互通信 或是與外部的基站通信。大量的傳感器可以保證精確探測一個很大的區(qū)域。通常傳感器節(jié)點有傳感器模塊、處理模塊、無線通信模塊和能量模塊。傳 感器模塊負責(zé)監(jiān)測信息的采集和數(shù)據(jù)轉(zhuǎn)換；處理模塊負責(zé)傳感器的操作，存儲 和處理自身采集的數(shù)據(jù)以及

6、其他節(jié)點發(fā)來的數(shù)據(jù)；無線通信模塊負責(zé)與其他傳 感器節(jié)點進行無線通信，交換控制消息和首發(fā)采集數(shù)據(jù)；能量供應(yīng)模塊為傳感 器節(jié)點提供所需的能量1為實現(xiàn)了減小能量消耗這個目標(biāo)，一方面可以把已有的路由技術(shù)應(yīng)用到無 線傳感器網(wǎng)絡(luò)中，另一方面也可以設(shè)計專門適用于該網(wǎng)絡(luò)的路由方法。例如： 數(shù)據(jù)收集方法，簇方法，給每個節(jié)點分配不同任務(wù)，以數(shù)據(jù)為中心的方法。根 據(jù)網(wǎng)絡(luò)的結(jié)構(gòu)，路由協(xié)議一般可以分成扁平網(wǎng)絡(luò)和分層網(wǎng)絡(luò)。在扁平網(wǎng)絡(luò)中， 每個節(jié)點都有相同的功能，而在分層網(wǎng)絡(luò)中，局部的節(jié)點組成簇，簇頭節(jié)點可 以調(diào)整數(shù)據(jù)量的大小來達到節(jié)約能量的目的?；谖恢玫穆酚墒褂霉?jié)點的位置 信息來中繼數(shù)據(jù)到目標(biāo)區(qū)域。2無線傳感器網(wǎng)絡(luò)中路

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

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

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

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

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

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

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

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

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

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

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

18、感器網(wǎng)絡(luò)的路由。最后，衷心感謝河北工業(yè)大學(xué)夏克文教授在百忙中審閱此論文，同時感謝 夏克文老師對本工作的指導(dǎo)。參考文獻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