智能信息處理論文

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

2、 影響因素以信息素形式表現(xiàn)出來(lái)。該路由方法的自組織、動(dòng)態(tài)和多路徑的特性 比較適合應(yīng)用于無(wú)線傳感器網(wǎng)絡(luò)的路由。關(guān)鍵詞：無(wú)線傳感器網(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中圖分類號(hào):TP18文

5、獻(xiàn)標(biāo)識(shí)碼:A1引言隨著微電子技術(shù)，計(jì)算技術(shù)和無(wú)線通信技術(shù)的進(jìn)步，制造低功耗的傳感器 在技術(shù)上和成本上已經(jīng)成為可能。傳感器具有信息采集、數(shù)據(jù)處理和無(wú)線通信 多種功能。通常傳感器探測(cè)它周圍的環(huán)境并生成電信號(hào)，并且處理這些信號(hào)使它們表現(xiàn)為傳感器監(jiān)測(cè)的目標(biāo)或發(fā)生事件的屬性。無(wú)線傳感器網(wǎng)絡(luò)(WirelessSensor Network)包含了很多傳感器節(jié)點(diǎn)，這些傳感器可以相互通信 或是與外部的基站通信。大量的傳感器可以保證精確探測(cè)一個(gè)很大的區(qū)域。通常傳感器節(jié)點(diǎn)有傳感器模塊、處理模塊、無(wú)線通信模塊和能量模塊。傳 感器模塊負(fù)責(zé)監(jiān)測(cè)信息的采集和數(shù)據(jù)轉(zhuǎn)換；處理模塊負(fù)責(zé)傳感器的操作，存儲(chǔ) 和處理自身采集的數(shù)據(jù)以及

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

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

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

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

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

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

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

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

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

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

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

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

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