牙說：接著上一篇繼續寫。




論文標題：An Energy-Efficient Ant-Based Routing Algorithm forWireless Sensor Networks
作者：Tiago Camilo, Carlos Carreto, Jorge Sá Silva, Fernando Boavida

正文：

2、相關工作
可以考慮無線傳感器網絡，如前所述，ad-hoc網絡。 然而，用于移動自組織網絡（MANET）的協議不提供傳感器網絡的一些要求：傳感器通常具有低功率電池，低存儲器，并且路由表隨著網絡長度而增長，并且不支持擴散通信。 這些是建立在能源效率最重要標準的基礎上設計新協議的主要原因。
[2]中描述的低能量自適應聚類層次結構（LEACH）可能是傳感器網絡區域中引用最多的協議之一。 它是一種用于傳感器網絡的，有持續的數據流動（無阻塞的傳感器活動）功能強大，高效的協議。 它使用分層拓撲的協議，隨機創建標簽頭，并呈現數據聚合機制。
? Power-Efficient GAthering inSensor Information Systems (PEGASIS), 是一種新開發的協議，它和leach協議類似，但是每輪所需能量更少（ 牙注：這里的每輪是什么意思？明白后補）。 在PEGASIS中，創建了鏈使得每個節點接收聚合信息并將其轉發到附近的鄰居。 它提出了允許無線電通信能量參數變化的機制。 與LEACH相比，PEGASIS協議在每輪獲得高達100％的能源成本改進[4]。 然而，這兩個協議在移動情況下都不適用，并且它們都假設數據包可以在簇頭聚合。
直接擴散（DD）[5]是一種以數據為中心的協議，它通過監視的數據而不是其網絡地址來定位節點。 在該協議中，應用程序負責查詢網絡的具體現象值。 滿足特定查詢的傳感器節點開始發送其數據。 基于接收器節點請求，該協議在構建其基于洪泛的路由方案時不考慮節點的可用能量。
Jeon等 [6]提出了一種節能路由協議，試圖解決延遲和能量問題。 基于AntNet協議[7]，該算法使用螞蟻信息素的概念來生成兩個優先級排隊，用于差分傳輸（ 牙注：所謂差分傳輸，就是發送端在兩條信號線上傳輸幅值相等相位相反的電信號，接收端對接受的兩條線信號作減法運算，這樣獲得幅值翻倍的信號）。 然而，由于保存兩個隊列需要不小的內存，這種方法在當前傳感器節點中可能是不可行的。 如果傳感器網絡非常密集，這可能會更加麻煩，因為每個設備上的路由表取決于鄰居的數量。
張等人 [8]，研究了三種不同的基于Ant的算法，用于WSN。 然而，作者只關注初始信息素分布的建立，擅長系統啟動。
在[9]中，作者提出了一種可以移植到WSN路由的Steiner Tree（斯坦納樹）的蟻群算法。 然而，對于具體的WSN要求，他沒有考慮任何變化，也沒有考慮到WSN性能所必需的能源管理。
上面提出的蟻群算法都假定WSN應用程序需要傳感器節點（端到端）之間的通信，在這樣的假設基礎上構建其算法。 然而，在大多數WSN場景中并不是這樣，大多數WSN場景從源節點（傳感器節點）到匯聚節點執行逐跳或單跳通信，負責從網絡收集傳感器數據。這些節點（ 牙注：這里的這些節點指的是源節點與匯聚節點嗎？）與正常的傳感器節點（更多的能量，更大的存儲能力和更大的處理能力）相比呈現出不同的特征，這些差異在所引用的算法中都沒有被考慮到。

3、基于蟻群的能量有效路由協議

當一個WSN協議被設計出來的時候，一定要考慮基礎算法的能量效率，因為這種類型的網絡（牙注：大概指的是無線傳感網吧）具有嚴格的功率要求。在本節中，我們提出了一種新的能量約束協議，EEABR協議，它基于蟻群優化啟發式，并且集中在主要的WSN約束上（牙注：這句話耐人尋味，有點不懂，明白后補）。

在實際部署的無線傳感網絡中，傳感器節點可能沒有補充能量的能力。這個假設要求我們必須強制使用節能算法來最大限度的提高網絡的使用壽命。相比之下，在及時傳輸網絡中，路由算法的目標是找到兩個設備（源和目的）之間的最短路徑，這可以通過選擇具有較少通信跳數的路徑輕松完成。在運行協議需要降低的通信延遲的WSNs中，這種要求被降到第二個階層，因為服務質量和服務意識沒有像在一般MANETs中那么重要。

本節的其余部分總結了EEABR背后的想法。 首先介紹基于螞蟻的基本路由算法。 接下來，介紹了基本算法的改進。 最后，提出了EEABR算法。

3.1 基于蟻群的基礎路由

ACO元啟發式已經成功應用于許多組合優化問題[13]。 其優化過程可以輕松實現用于WSN的蟻群路由算法的優化。 AntNet [7]算法的基本實現可以非正式地描述如下。

1.定期從每個網絡節點發起一個前向螞蟻k，其任務是找到一個直到目的地的路徑。 每個訪問節點的標識符被保存到被螞蟻攜帶的存儲器Mk中。

2.在每個節點r，前向螞蟻使用ACO元啟發式中提出的同一個概率規則來選擇下一跳節點（牙注：下圖就是那個概率規則）：

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?

p_k(r,s)是螞蟻k選擇從節點r移動到節點s的概率，T是每個節點上的路由表，用于存儲每個連接上的信息素濃度（牙注：T(r,s)代表的是r到s這條鏈路上的信息素濃度），E代表可見性函數1/(C-e_s)（C是節點的初始能量水平，e_s是節點s的實際能量水平）（牙注：就是說一個節點的消耗能量越大，到這個節點的概率就越小），α和β是控制信息素與可見度的相對重要性的參數。選擇概率是可見度（表示節點能量越高越可能被選中）和信息素濃度（即如果在連接(r,s)的流量越多這條連接越可能被選中）之間的折衷（牙注：這個α和β感覺可以好好玩一下）。

3.當前向螞蟻到達目的地節點時，它被轉換成一個后向螞蟻（牙注：這個大概是說回發一個數據包吧），其任務是更新用于到達目的地的路徑的信息素濃度，并將其存儲在其存儲器中（牙注：或者是將更新完的信息素濃度存儲到存儲器中，這個存儲器是節點的存儲器嗎？還是隨包攜帶的路由表啊？）。

4.在返程螞蟻k開始其返程之前，目的地節點計算螞蟻在旅途中會下降的信息素濃度的量（牙注：這里的信息素濃度下降是什么意思？誰的信息素濃度會下降啊？）（牙注：下圖就是計算的那個公式）：

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ??

N是節點的總數量，Fd_k是前進螞蟻旅行的距離（也就是它存儲器中存著的通過節點的數量）。（牙注：也就是說通過節點越多，信息素濃度下降越快咯）

5.每當返程螞蟻從節點s爬到節點r的時候，節點r將以以下方式更新其路由表：

ρ是一個系數，(1-ρ)代表距離上一次T_k(r,s)更新后的信息素揮發情況。

6.當返程螞蟻到達創建它的節點時，其任務完成，這只螞蟻消失。

通過執行該算法幾次迭代，每個節點將能夠知道向特定目的地發送分組時的最佳鄰居是哪個（根據由等式2表示的最優函數）（牙注：為什么是等式2嘞？僅僅根據節點跳數來確定那條路徑是最佳路徑感覺有失偏頗）。

3.2 為WSN優化蟻群路由

在本節中，我們提出了上一節中描述的基本的螞蟻路由算法的兩個改進，以便減少傳感器節點中使用的內存，并考慮螞蟻發現的路徑的能量質量。

在基本算法中，前向螞蟻的目的節點是不確定的，這意味著傳感器節點之間必須能相互通信，每個節點的路由表必須包括其鄰域中所有傳感器節點的標識和其對應路徑的信息素濃度。在大型網絡中，由于節點需要大量內存來保存所有關于鄰域的信息，這可能會成為一個問題。但是，這個算法能夠被輕松地改變來達到節省內存的目的。如果一只螞蟻要直接到sink節點，那么路由表只需保存位于sink方向的鄰居節點（牙注：sink方向？這個怎么確定？），這大大減少了路由表的大小，從而減少了節點所需的內存。

如導言中所述，傳感器節點是能量容量非常有限的設備。也就是說，我們在選擇傳感器節點到sink節點之間的路徑的時候，不僅僅要考慮距離（路徑的節點數量），還要考慮該條路徑的能級（牙注：能量等級大概是說能量的檔次問題吧）。例如，我們應當優選選擇具有較高能級距離長的路徑，放棄能級低距離短的路徑。（牙注：這說明能量的吸引力>距離）

考慮到基本算法路徑的能量質量，提出了一種新函數來確定返程螞蟻在返程過程中下降的信息素濃度量：

E_k是由前進螞蟻k攜帶的它前進路上節點能級的新矢量（牙注：這句話有毒，附原句：where?E_k is a new vector carried by forward ant k with the energy levels of the nodes of its path，矢量是社么玩意兒？），C是節點的初始能級，Avg(E_k)是向量值的平均值，Min(E_k)是 向量的最小值。（牙注:回來補充，C（節點的初始能量）越高，變化越小；Avg(E_k)（向量值的平均值）越大，變化越大；最小值越大，變化越小，還是不明白，節點的能量本來很高不是很好的事情嗎。。）

3.3 無線傳感網中的基于蟻群的能量有效路由

在本節中，我們提出進一步改進上一節中描述的路由算法的方法，以減少與螞蟻相關的通信負載和通信所花費的能量。 我們還提出了更新信息素濃度的新函數。

已經證明，節點花費在通信（接收和發送數據）上的能量遠大于數據處理和存儲器管理上的能量。WSN的關注點之一是最大限度地延長網絡的使用壽命，這意味著盡可能多地節省能量，所以我們優選的是路由算法可以在網絡節點中執行盡可能多的處理而不是傳輸所有從螞蟻到sink節點的數據。（牙注：這句話很懵。。。附上原句：it would be preferable that the routing algorithm could perform as much processing as possible in the network nodes, than transmitting all data through the ants to the sink-node to be processed there）。事實上，在巨大的傳感器網絡中，節點數目可以輕松到1000個以上，螞蟻的存儲數據將會非常龐大，所以通過網絡發送節點是不可行的。（牙注：通過網絡發送是不行的。。。那么通過什么發送是可以的？）

為了實現這些想法，我們做出如下改進：每個螞蟻的內存M_k減少到兩個記錄——最后兩個訪問的節點。由于螞蟻爬過的路徑沒有保存在它的記憶之中，因此我們必須在節點之中創建一個記錄，用來記錄每只到達和出去的螞蟻。每條記錄都保存著之前的節點、接下來要去的節點、螞蟻的標識以及超時值（牙注：這里的超時值很有意思，附上原句：a timeout value 懂后解釋）。每當收到一只前向螞蟻的時候，節點就查看存儲器，看看有沒有這只螞蟻的標識，看看這只螞蟻是不是已經爬過又爬回來了（牙注：這里的語言很白話，就是這么個意思）。如果沒有找到這只螞蟻的記錄（牙注：這說明這只螞蟻第一次經過這里），節點就保存所需的信息，重新啟動定時器，把螞蟻轉發到下一個節點（牙注：轉發方法應該還是那個概率的游戲），如果在節點存儲器中發現了這只螞蟻的記錄，就把這只螞蟻搞滅亡。當一個節點收到一只返程螞蟻的時候，它會搜索它的存儲器，找到這只螞蟻的下一個去處。（牙注：要是螞蟻太多，節點的存儲器會不會也承受不了？定時器解決了這個問題）定時器用于刪除標識返程螞蟻的記錄（牙注：這里莫明，附上原句：?The timer is used to delete the record that identifies the backward ant，牙的理解：如果節點存儲器中的每條記錄都是有時間限制的，在時間到之前還沒有等到相應的返程的螞蟻，這條記錄就消失了，解決了可能存在的存儲量過大的問題。問題：是不是一條記錄等到返程螞蟻之后，這條記錄也會被消除呢？我猜是的。。。）

前向螞蟻k已經沒有矢量E_k了，它現在就帶著到目前這個節點為止的平均能量（EAvg_k）和最小能級（EMin_k）（牙注：這個是個什么東西，是誰的平均能量與最小能級）這些值被每個收到前向螞蟻的節點更新。

當前向螞蟻到達sink節點的時候，這些值用于計算對應的返程螞蟻使用的信息素濃度。（牙注：下式用于計算差值，分析一下：最小能級越大，差值越大，平均能級越大，差值越小）

通過這些改變，可以將螞蟻的長度（牙注：數據包的長度）減小?700％（牙注：減少700%也是很有意思的），并保存每個螞蟻每一跳傳輸約250個字節（牙注：此句拗口，附上原句：?save on each ant hop the transmission of ~250 bytes）。 這是一個重要的成就，因為它可以節省傳感器節點上的寶貴能量。

因為有15個節點的路徑可能與僅僅有5個節點的路徑具有相同的平均能量值，所以如等式4那樣，僅僅利用作為路徑能級的函數ΔT_k不能帶來優化的路線。因此，ΔT_k計算時必須有兩個參數，能級和路徑的長度。如等式5所示，可以引入Fd_k來解決，Fd_k代表的是前向螞蟻已經訪問的節點數量。

用于更新每個節點上的路由表的方程現在更改為：

其中φ是系數，Bd_k是到達節點r的返程螞蟻k的行進距離（被訪問節點的數量）（牙注：這是說越靠近sink節點，加的信息素越多）。這兩個參數將迫使螞蟻在其到達源節點的途中松散部分信息素強度。 這種行為背后的想法是建立一個更好的信息素分布（靠近sinknode的節點將具有更多的信息素水平）（牙注：就是說越靠近目標越不能瞎出亂子），這樣將強制偏遠節點找到更好的路徑。由于信息素適應（牙注：？名詞翻譯，附上原句：pheromone adaptation）非?？?#xff0c;所以這個行為在源節點能夠移動的時候非常重要。

4 實驗結果

在本節中，我們介紹了第3節中描述的三種算法所獲得的實驗結果：第3.1節中描述的基于螞蟻的基本路由算法（BABR），第3.2節中介紹的改進的基于螞蟻的路由算法（IABR） 以及第3.3節提出的節能螞蟻基于路由算法（EEABR）。 使用眾所周知的ns2模擬器[14]，使用兩射線地面反射模型（牙注：這個東西很高大上的樣子。。。）對算法進行了測試。

為了更好地了解三種算法之間的差異，使用了三種不同的方案，每種方案都可以用來代表真實的WSN部署環境。在所有情況下，節點都以隨機方式部署，因為在實際的傳感器網絡中，由于環境特性，設備部署通常不能由操作員控制。部署的傳感器節點的數量在10~100個之間變化。在模擬面積方面也有所變化，為保證節點之間的連通性，按照如下規則選擇模擬面積——200×200 m²（10節點），300×300 m²（20節點），400×400 m²（30節點），500×500 m²（40節點）和600×600 m²（50,60,70,80,90和100個節點）。對于每個環境，我們使用以下四個度量用于比較算法的性能：平均能量，其給出了在模擬結束時所有節點的平均能量值;最小能量，其給出所有節點的最低能量;標準偏差，其給出所有節點上的能級之間的平均差異;最后是能量效率，其給出了總消耗能量與接收節點接收的分組數之間的比率。（牙注：覺得這一段是干貨，以后在選擇分析參數的時候可以借鑒這里的四個度量）

第一種情況模擬靜態WSN，傳感器節點隨機部署，以監測靜態現象?，F象（牙注：這個單詞翻譯無能，現象是什么鬼。。。之后附上全部原句）和接收節點的位置是未知的（牙注：原句：The location of the phenomenon and the sink-node are not known.?）節點負責監視現象（牙注：orz....），并且將相關的傳感器數據發送到接收節點。在這種情況下，現象（牙注：orz........）附近的節點在能源消耗方面將受到影響，因為它們將被迫周期性地傳輸數據。圖1給出了所研究參數的仿真結果。 在大多數情況下（從10到100個節點），EEABR協議給出了最好的結果。?在圖1b），當網絡有30個節點時，兩個協議（BABR和IABR）中的最小能量都呈現非常低的值，但是在EEABR協議中卻不是這樣的。這種情況在圖1c）中也出現了——標準差顯示出相同的特征?？紤]到使用的拓撲圖，這個又好解釋了，因為從源到匯聚節點的通信路徑很少（牙注：為什么好解釋還沒有很明白，明白再補）。

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 圖1 傳感器網絡中靜態環境下的協議性能比較（牙注：翻得很傻。。。。）

結果如圖1所示。 2對應于第二種情況，第二種情況是可移動的。 與先前情況的結果相比，現象移動性降低了算法的性能，這是可以理解和預期的，因為更多的節點成為數據包的來源（牙注：為什么可以移動會使更多的節點成為數據包的來源），增加了網絡中的數據包數量。 與其他協議相比，EEABR協議再次表現出最好的結果，結果可以輕松地與所有環境變量都是靜態的情況進行比較。

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 圖2?傳感器網絡中動態環境下的協議性能比較

最后的研究是模擬網狀傳感器網絡，這些網絡由具有不同功能的幾個節點組成。在每個網絡上，使用三個能級：50，30和20焦耳。這些級別均勻分布在節點上。圖3顯示了仿真結果。與以前的研究相比，EEABR方案具有更好的最終結果。這可以通過協議的適應性來解釋，該協議有效地嘗試平衡所有節點上的能量級別。這個結論在圖3.d）中更為明顯。與其他算法相比，EEABR的標準偏差顯著降低。在平均能量水平方面，EEABR呈現最佳效果。與IABR相比，平均值之間的差異在3％和10％之間變化，而與BABR相比，差異在17％和25％之間變化。在模擬結束時節點的最小能量方面，沒有算法可以避免“死”節點的存在，但是BABR和IABR呈現出兩個“死”節點，與EEABR協議僅提供一個。這種現象的產生式因為隨機節點分布——其中只有兩個節點負責在源節點和宿節點之間提供連接——因為該現象是靜態的。（牙注：這句話翻譯無能，理解無能，附原句：This is due to the random node distribution, where only two nodes were responsible to provide connectivity between the source and the sink-node, since the phenomenon was static.?）

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?圖3 具有不同初始能級傳感器網絡下的協議性能分析

關于能源效率，結果在所有情況下非常相似。 EEABR和IABR呈現最好的結果且它們的值相近，這是因為這兩個協議都是能量感知型（牙注：能量感知型？新名詞，打標記）的。然而，就其它參數而言，兩種協議之間的差異變大，EEABR性能更好，因為它顯著降低了通信中消耗的能量。BABR算法對于所有研究的參數呈現最差的結果，盡管在某些情況下，由于IABR在減少交換消息中的開銷方面效率低下，它達到與IABR協議相同的值。

5.結論

在本文中，我們研究了蟻群優化元啟發式在無線傳感器網絡中解決路由問題的應用。提出了基于蟻群算法的基本路由算法，并考慮并實現了針對無線傳感網絡特性（低能級、低處理能力、低存儲容量）的幾點改進。所得的路由協議（EnergyEfficient Ant Based Routing，EEABR）使用輕量級螞蟻來查找傳感器節點和宿節點之間的路由路徑——這些路由路徑在距離和能級方面進行了優化。這些特殊的螞蟻可以最大限度地減少溝通負擔，并最大限度地節省能源，有助于延長無線網絡的使用壽命。實驗結果表明，該算法在不同的WSN場景中有非常好的結果。

作為未來的工作，我們打算研究使用初始信息素水平填充路由表的初始化方法。 如文獻[8]所示，這種機制可以進一步提高網絡的效率。另一個待研究的方法是集成多個接收節點。

致謝以及文獻引用部分不翻譯了，原文如下：

ACKNOWLEDGMENTS

The work presented in this paper is partially financed by the Portuguese Foundationfor Science and Technology, FCT through the 6Mnet POSI/REDES/44089/2002 project.This work has been partly supported by the European Union under the E-Next FP6-506869 NoE.

References

1 Estrin, D., et al., “Embedded, Everywhere: A research Agenda for Network Systems of EmbeddedComputers”, National Research Council Report, 2001

2 Handy, M., Haase, M., Timmermann, D., “Low Energy Adaptive Clustering Hierarchy withDeterministic Cluster-Head Selection,” 4th IEEE International Conference on Mobile andWireless Communications Networks, Stockholm, 2002

3 Lindsey, S., Raghavendra, C., “PEGASIS: Power Efficient GAthering in Sensor InformationSystems”, ICC, 2001

[4] Lindsey, S., Raghavendra, C., Sivalingam, K., “Data Gathering in Sensor Networks usingthe EnergyDelay Metric”, 2000

5 Intanagonwiwat, C., Govindan, R., Estrin, D., “Directed Diffusion: a scalable and robustcommunication paradigm for sensor networks”, ACM Press, 2000

6 Jeon, P., Rao, R., Kesidis, G., Two-Priority Routing in Sensor MANETs Using Both Energyand Delay Metrics in preparation, 2004

7 Di Caro G., Dorigo M., "AntNet: Distributed Stigmergetic Control for CommunicationsNetworks", Journal of Artificial Intelligence Research (JAIR), Vol. 9, Pag. 317-365, 1998

8 Zhang, Y., Kuhn, L., Fromherz, M., ?Improvements on Ant Routing for Sensor Networks”.In: Ants 2004, Int. Workshop on Ant Colony Optimization and Swarm Intelligence, Sept.2004

9 Singh, G., Das, S. Gosavi, S., Pujar, S., “Ant Colony Algorithms for Steiner Trees: An Applicationto Routing in Sensor Networks”, Recent Developments in Biologically InspiredComputing, Eds. L. N. de Castro, F. J. von Zuben, Idea Group Publishing, pp. 181-206,2004

10 Zuniga, M. Z.; Krishnamachari, B. "Integrating Future Large-Scale Wireless Sensor Networkswith the Internet" - Department of Electrical Engineering, UNiversity of SouthernCalifornia, 2002

11 Alonso, J., Dunkels, A., Voigt. T, ?Bounds on the energy consumption of routings in wirelesssensor nodes” WiOpt'04: Modeling and Optimization in Mobile, Ad Hoc and WirelessNetworks, Cambridge, UK, March 2004

總結

以上是生活随笔為你收集整理的An Energy-Efficient Ant-Based Routing Algorithm for Wireless Sensor Networks (无线传感网中基于蚁群算法的能量有效路由)2的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。