一種生物啟發(fā)的無線融斷網絡數(shù)據傳輸算法*

姚紅娟，華 翔,2，王 海，李寶華

(1.西安工業(yè)大學 電子信息工程學院，西安 710021；2.西安工業(yè)大學 兵器科學與技術學院，西安 710021；3.北方特種能源集團 西安慶華公司，西安 710025)

隨著移動自組織網絡的發(fā)展，越來越多的數(shù)據通過無線網絡傳輸。傳統(tǒng)的無線自組織網絡，數(shù)據傳輸過程中要求源端和目的端至少存在一條可靠路徑。然而，在一些實際的復雜網絡場景中，如災區(qū)、戰(zhàn)場、軍事行動中，常會出現(xiàn)因節(jié)點移動，資源受限，信號衰減等因素，造成網絡在某些時刻不聯(lián)通情況[1]。為了在復雜環(huán)境中實現(xiàn)有效的數(shù)據通信，無線融斷網絡[2]的概念應運而生。無線融斷網絡是一種特殊的自組織網絡，無法保證網絡拓撲的穩(wěn)定性和全聯(lián)通性，依靠節(jié)點的移動形成局部的融合和分割網絡，更適合在復雜、惡劣場景下的一種間斷通信，能更好的滿足實際的自組網需求。

針對拓撲動態(tài)變化、鏈路不穩(wěn)定導致的通信困難問題，已有學者展開了研究。文獻[3]提出了一種新的基于混合社區(qū)的數(shù)據傳輸機制，構建基于混社區(qū)的網絡模型，進行中繼選擇和轉發(fā)策略制定，雖然改善了網絡性能，但是該方法未考慮網絡的負載問題。文獻[4]提出了基于節(jié)點通信的數(shù)據傳輸與管理方法，通過社會壓力度量節(jié)點間的連接強度，開發(fā)了自適應控制復制傳輸模式，降低了網絡負擔和網絡開銷。然而，在復雜的社區(qū)網絡環(huán)境中，信息在傳播過程中會受到各種因素的干擾，數(shù)據投遞率較差。文獻[5]提出了一種高效的數(shù)據包迭代傳輸算法，在當前節(jié)點的通信區(qū)域內選擇數(shù)據傳輸能力好的中心節(jié)點，有效提高數(shù)據包的交付率。但是該方法的不足是端到端的時延較大。文獻[6]提出了文件發(fā)送序列調度算法，根據文件傳輸時耗與鏈路持續(xù)時間，使得在短暫的通信持續(xù)時間內成功傳輸文件。當文件的大小超過設定值時，該算法會導致數(shù)據傳輸失敗，不能實現(xiàn)盡力投遞的目標。文獻[7]提出了消息副本轉發(fā)算法，從節(jié)點相遇概率和消息重復擴散角度分析，給出了評估相遇信息價值的時效指標和節(jié)點移動偏離指標，合理地選擇消息傳輸中繼節(jié)點并提高消息投遞效率。但是，該算法不能用于網絡中所有節(jié)點性能相同的場景。文獻[8]提出了劃分興趣社區(qū)的路由算法，利用節(jié)點接收的歷史消息次數(shù)和消息之間的相似度，量化出節(jié)點對各類消息的興趣程度，然后把節(jié)點劃分到相對應的興趣社區(qū)。該算法雖然降低了通信開銷，但帶來的較大的傳輸時延。文獻[9]提出了一種用于復雜機會網絡的低延遲廣播算法，在網絡中進行消息廣播時，算法會分析在指定的傳輸時間片上的鏈路是否滿足連續(xù)干擾消除條件，實驗表明該方法提高了信息傳輸效率。因為該算法使用廣播傳輸機制，導致較大的傳播開銷。文獻[10]提出了基于節(jié)點效用值的機會網絡轉發(fā)算法，考慮節(jié)點相遇概率、節(jié)點變化率、節(jié)點傳輸容量、節(jié)點連接容量等因素，建立了節(jié)點效用值模型。在此基礎上選擇轉發(fā)節(jié)點發(fā)送消息，有效降低了網絡開銷和平均中繼次數(shù)，但在實際的動態(tài)網絡中，節(jié)點效用值計算極其困難，導致傳輸成功的消息數(shù)較少。文獻[11]提出了基于轉發(fā)概率的動態(tài)數(shù)據轉發(fā)策略，根據節(jié)點能量消耗和消息傳輸延遲計算出節(jié)點的傳輸概率和轉發(fā)概率，使節(jié)點獲取的消息能夠以盡可能低的能量消耗和傳輸延遲發(fā)送到匯聚節(jié)點，該算法有效延長了網絡壽命，降低了傳輸能耗。該方法針對不同類型的傳感器節(jié)點組成的網絡，所以其在同構網絡中的投遞效率下降。以上的研究雖在解決網絡通信方面取得了一些成果，但大多都基于傳統(tǒng)方法實現(xiàn)，考慮了傳輸成功率，延遲以及網絡開銷的某一方面性能，其可擴展性和效率受到一定的限制。近年來，生物啟發(fā)方法受到廣泛關注，其高度的自然適應性成為解決網絡問題的有效手段[12]。多頭絨泡菌生物具有強大的計算和移動能力，能夠形成復雜的網絡系統(tǒng)，可引導全新高效的智能算法[13]。

本文利用多頭絨泡菌的智能特性，提出了一種生物啟發(fā)的無線融斷網絡數(shù)據傳輸算法，實現(xiàn)間斷性連通環(huán)境下的數(shù)據通信。分析多頭絨泡菌的智能特性和無線融斷網絡的動態(tài)拓撲，搭建了無線融斷網絡的仿生模型；研究了拓撲動態(tài)變化過程中的數(shù)據傳輸問題，優(yōu)化了下一跳節(jié)點選擇方法，完成分割網絡間的數(shù)據逐跳傳輸。通過設計實驗與傳統(tǒng)算法進行對比。

1 仿生網絡模型建立

1.1 多頭絨泡菌特性分析

多頭絨泡菌在路徑尋優(yōu)方面展現(xiàn)高度的智能性和自適應性，當該菌在多個食物源的環(huán)境中攝食，能夠向外擴散連接食物源形成管道網絡，如圖1所示。具有以下特性：① 當初始的管道網絡形成后，如果有新的食物源加入，該菌的原生質管道會分叉成支路來覆蓋食物源。② 當食物源被消化完全后，連接該食物源的管道會萎縮消失。③ 當光照等不利因素影響時，原生質管道會消失。

圖1 多頭絨泡菌

基于對多頭絨泡菌攝食網絡形態(tài)、特性的研究，可將尋找路徑的機制融合到一個數(shù)學模型中[14]。在該網絡中，管道內流動的原生質流滿足哈根-泊肅葉方程：

(1)

(2)

多頭絨泡菌管道的形成過程有著明顯的正反饋機制，如圖2所示。當管道中的原生質流通量增加時，導通性也會增大；而導通性的增大又會引起管道的原生質流通量增加。

圖2 正反饋機制

導通性Dij隨著原生質流通量Qij變化為

(3)

式中：δ為管道的收縮速率；f(·)為單調遞增函數(shù)，同時滿足f(0)=0。式(3)描述了沒有原生質流的管道會逐漸消亡。

為了模擬多頭絨泡菌攝取多個食物源的過程，式(3)中f(|Qij|)采用S型函數(shù)為

(4)

此S型函數(shù)變化規(guī)律體現(xiàn)多頭絨泡菌的生長特性。當原生質流通量增大時，管道的直徑由于其生物特性會趨于穩(wěn)定，而不會出現(xiàn)無限量增大的情況；反之，當通量減小時，管道的直徑不會因為流量的變化產生太敏感的反映。

1.2 無線融斷網絡動態(tài)拓撲

無線融斷網絡的具有一定局限性，無法實現(xiàn)節(jié)點之間全局信息共享，需要充分利用節(jié)點移動帶來的相遇機會，盡量在鏈路持續(xù)時間內完成數(shù)據交互，解決在間歇性連通的網絡上的數(shù)據傳遞。無線融斷網絡具有：① 節(jié)點分布稀疏、資源有限、自主移動頻繁；② 端到端鏈路不穩(wěn)定，缺乏持續(xù)、可靠的連接；③ 通信網絡伴隨分割和融合現(xiàn)象，呈現(xiàn)間歇性連接狀態(tài)。

基于無線融斷網絡的特點，無線融斷網絡的拓撲結構示意圖如圖3所示。t1時刻源節(jié)點S與目的節(jié)點D位于不同的連通域中，沒有直接的通信路徑，因此，S先將數(shù)據發(fā)送給鄰居節(jié)點2，隨后節(jié)點2將數(shù)據放入本地緩存等待合適的傳輸機會，經過一段時間，t2時刻節(jié)點2運動到節(jié)點3的通信范圍內，節(jié)點間是強連接的，此時可以與其鄰居建立路由，將數(shù)據轉發(fā)給節(jié)點3，在t3時刻，當節(jié)點3與目的節(jié)點D位于同一個連通域內完成數(shù)據傳輸。

圖3 無線融斷網絡拓撲形成過程

1.3 無線融斷網絡仿生模型

基于生物智能特性和網絡拓撲研究，文中借鑒多頭絨泡菌在動態(tài)環(huán)境中的自適應性，選擇最佳的下一跳節(jié)點，優(yōu)化無線融斷網絡的連接和鄰居個數(shù)，完成數(shù)據投遞。將多頭絨泡菌引入無線融斷網絡中，搭建了無線融斷網絡仿生模型，如圖4所示。

圖4 無線融斷網絡仿生模型

無線融斷網絡與多頭絨泡菌覓食網絡有較強的相似性，概括為：① 實際的覓食環(huán)境和網絡環(huán)境都復雜多變的，覓食過程中食物源的大小、數(shù)量、位置可變，無線融斷網絡節(jié)點自主頻繁移動。② 它們都需要維持對環(huán)境較強的自適應能力，更正錯誤路徑，提高網絡性能。③ 多頭絨泡菌通過對食物源的選擇形成網絡，無線融斷網絡需要對下一跳的選擇形成網絡拓撲進行數(shù)據傳輸。

文中采用無量綱分析方法，將式(1)和式(3)遷移到無線融斷網絡中。用φij代替Dij，表示節(jié)點i，j間數(shù)據傳輸能力。用dij代替Lij，表示節(jié)點i，j間距離，是時變量，所以用Δdij(t)表示。最后，用eij代替ΔPij，表示鏈路生存能力。因此式(1)可以轉化為

(5)

多頭絨泡菌在覓食過程中展現(xiàn)自組織、自優(yōu)化等智能特性，形成連接各食物源的覓食網絡，是通過Dij的進化實現(xiàn)自適應調節(jié)。文中將其用于網絡拓撲形成中，即節(jié)點同周圍建立連接通信關系的過程。網絡拓撲形成是節(jié)點轉發(fā)消息和路由選擇的基礎，把網絡節(jié)點看做食物源，節(jié)點間的數(shù)據鏈路看做多頭絨泡菌運輸營養(yǎng)的管道。當初始網絡建立后，多頭絨泡菌通過自適應機制強化有用的連接，去除冗余的連接，形成一個高功效的網。因此，可通過Δdij(t)的進化實現(xiàn)下一跳節(jié)點的自適應選擇為

(6)

式中：f(|Qij|)為S型函數(shù)，由式(4)可得δ為Δdij(t)的衰減率。

2 生物啟發(fā)的數(shù)據傳輸算法

2.1 優(yōu)化下一跳節(jié)點選擇策略

為了實現(xiàn)網絡非聯(lián)通時刻的數(shù)據傳輸，文中將無線融斷網絡拓撲形成過程劃分為多個時間片，在每個時間片上，通過式(6)的自適應選擇機制，完成鄰居節(jié)點的選取。文中采用簡單平均的方法計算當前時間片內節(jié)點間的平均距離。假設在一個時間片T中，網絡中有n個節(jié)點，任意節(jié)點都是從1到n輪流選擇，則節(jié)點間平均距離表示為

(7)

數(shù)據傳輸首先需要選擇最佳的下一跳節(jié)點。通過式(7)計算，得出當前時間片內節(jié)點間的平均距離。在此基礎上，進一步計算最佳的下一跳節(jié)點概率值。假設節(jié)點i從鄰居節(jié)點中選取最佳下一跳節(jié)點j的概率表示為

(8)

式中：k為節(jié)點k，屬于當前聯(lián)通網絡內的節(jié)點集；β為一個大于0的整數(shù)；dik為節(jié)點i到節(jié)點k的距離。式(8)表明在當前時間片內，距離當前節(jié)點越遠的節(jié)點被選為最佳鄰居節(jié)點的概率越大。

2.2 數(shù)據傳輸策略

數(shù)據傳輸應使網絡中所有節(jié)點盡最大可能具有分組轉發(fā)的機會，并盡力將分組向目標節(jié)點和目標網絡投遞。對于不穩(wěn)定鏈路和拓撲動態(tài)變化的無線融斷網絡，文中提出了生物啟發(fā)的數(shù)據傳輸算法，采用存儲-攜帶-轉發(fā)策略，需要充分利用最佳下一跳節(jié)點暫存數(shù)據。隨著節(jié)點的移動，兩分割網絡短暫融合后必須盡快將數(shù)據交換完畢，實現(xiàn)間斷性連通環(huán)境下的數(shù)據通信。節(jié)點均勻的分布在整個仿真區(qū)域內，其中源節(jié)點和目的節(jié)點位置已知。根據式(8)計算出鄰居節(jié)點當選下一跳節(jié)點的概率值，選出概率值最大的節(jié)點當選最佳下一跳，如果該節(jié)點超時，則選擇概率值次最大的節(jié)點與當前節(jié)點建立連接。通過邊路由-邊傳輸?shù)霓D發(fā)機理完成數(shù)據傳輸。生物啟發(fā)的數(shù)據傳輸算法步驟:① 初始化網絡中的節(jié)點集合，給定源節(jié)點和目的節(jié)點的起始位置。② 按照隨機路點移動模型設置節(jié)點的移動規(guī)律。③ 根據式(7)，計算當前時間片內，任意兩節(jié)點間的平均距離。④ 根據式(8)，計算節(jié)點當選下一跳的概率值，并采用降序原則排序，存入臨時矩陣變量。⑤ 選取矩陣首行對應的節(jié)點，判斷節(jié)點停留時間是否超時，若是，刪除當前節(jié)點，繼續(xù)執(zhí)行③；否則節(jié)點當選為最佳下一跳。⑥ 判斷下一跳是否為目的節(jié)點，若是，完成數(shù)據路由轉發(fā)；否則當前節(jié)點作為根節(jié)點繼續(xù)搜索它的下一跳，執(zhí)行③。

3 仿真及分析

3.1 參數(shù)優(yōu)化

運用ONE模擬器，將文中算法與三種傳統(tǒng)算法(Epidemic，Spray & Wait,Prophet)進行性能對比，驗證提出算法的有效性。初始階段，節(jié)點在仿真區(qū)域內均勻分布，其他仿真參數(shù)設置見表1。

表1 仿真參數(shù)設置

仿真中選取投遞成功率、網絡負載率、平均投遞延遲、平均跳數(shù)4個指標衡量算法性能。其中，投遞成功率指目的節(jié)點成功收到的數(shù)據包個數(shù)與仿真時間內網絡產生的數(shù)據包總數(shù)之比。網絡負載率指網絡中所有節(jié)點轉發(fā)數(shù)據包的總數(shù)和成功投遞數(shù)據包總數(shù)的比值。平均投遞延遲指成功投遞到目的節(jié)點的數(shù)據包產生到投遞花費時間的平均值。平均跳數(shù)體現(xiàn)路由算法的整體性能，指網絡中所有消息的副本經歷的跳數(shù)總和與網絡中生存的所有消息數(shù)量之比[15]。

3.2 結果分析

數(shù)據包生存時間(Time To Llive,TTL)是用于衡量數(shù)據包在網絡中的時間是否太長而應被丟棄的字段。較大的數(shù)據包TTL意味著數(shù)據包能夠在網絡中存活更長時間，將對路由算法產生重要的影響。文中通過改變TTL大小，研究它對以上4種路由性能的影響。

1) 數(shù)據包TTL對投遞成功率的影響。對于不同數(shù)據包TTL下投遞成功率的變化情況。按照表1的仿真參數(shù)進行設置，其中將數(shù)據包TTL從初始的10 000 s以步長4 000 s逐步增加到26 000 s，得到Message Stats Report報告。該報告是以鍵值對的形式存儲仿真數(shù)據。提取各個算法對應的投遞成功率的值，得到4種算法的投遞成功率隨數(shù)據包TTL變化曲線如圖5所示。

從圖5可看出，隨著數(shù)據包TTL增大，Epidemic、Spray & Wait、Prophet算法的投遞成功率保持穩(wěn)定值且處于較低水平；本文算法投遞成功率出現(xiàn)微小范圍波動并處于較高水平。出現(xiàn)該結果的原因是：隨著數(shù)據包TTL增大，會導致使用洪范策略時節(jié)點緩存中消息副本積壓，降低了消息的投遞率。數(shù)據包TTL增大降低了因TTL超時而丟棄數(shù)據包的個數(shù)，文中算法考慮節(jié)點的移動性，在數(shù)據轉發(fā)時通過最佳概率判斷，選擇了最優(yōu)的下一跳節(jié)點，而不是向所有鄰居節(jié)點轉發(fā)數(shù)據，因此投遞成功率較高。

圖5 不同數(shù)據包TTL下的投遞成功率

2) 數(shù)據包TTL對平均投遞延遲和網絡負載率的影響。將Random Way Point移動模型的仿真熱生時間設置為1 000 s，仿真開始時，容易產生失真，放棄前1 000 s數(shù)據。通過改變數(shù)據包TTL大小，得到每個算法對應的平均投遞延遲和網絡負載率值，繪制成如圖6所示。

圖6 不同數(shù)據包TTL下的平均投遞延遲和網絡負載率

從圖6可以看出，隨著數(shù)據包TTL增大，文中算法的平均投遞延遲和網絡負載較小，而其他算法的投遞延遲較長且網絡負載較大。這是因TTL增大，數(shù)據包存活時間更長，節(jié)點中緩存的數(shù)據包攜帶的時間也延長，增大了投遞延遲；與此同時，節(jié)點能量消耗加快，網絡負載隨之上升。文中算法采用生物啟發(fā)方法進行下一跳節(jié)點的自適應選擇，能夠在節(jié)點相遇的短暫時間內，完成數(shù)據的交互，有效縮短了投遞延遲、降低了網絡負載。對以上三個方面的實驗，采用加權平均的方法，可得文中算法在投遞率、延遲、負載率方面綜合提高了33%。

3) 數(shù)據包TTL對平均跳數(shù)的影響。將消息的生成間隔設置成25 s～35 s，通過改變數(shù)據包TTL大小進行仿真。探究數(shù)據包TTL從10 000 s增加到26 000 s，平均跳數(shù)改變情況。提取仿真報告的結果，得到4種算法的數(shù)據包TTL與平均跳數(shù)曲線如圖7所示。

圖7 不同數(shù)據包TTL下的平均跳數(shù)

從圖7可看出，隨著數(shù)據包TTL增大，各個算法的平均跳數(shù)未發(fā)生明顯變化。平均延遲不僅取決于跳數(shù)的多少，與每一跳的等待時間也有關系。文中算法的成功傳輸消息的平均跳數(shù)略大于Prophet和Spray & Wait，卻小于Epidemic。這是因TTL增大，數(shù)據包存活時間更長，文中算法不停在尋找最佳的下一跳節(jié)點的過程中，增大了平均跳數(shù)實現(xiàn)消息盡力投遞。而基于洪泛的Epidemic不控制消息副本，轉發(fā)消息的平均跳數(shù)更高。Prophet和Spray & Wait的平均跳數(shù)雖然小，但犧牲平均延遲等性能。

4 結 論

1) 基于無線融斷網絡的弱連接和動態(tài)拓撲，提出了一種生物啟發(fā)的數(shù)據傳輸算法。

2) 通過搭建的無線融斷網絡仿生模型，用網絡中的物理量描述了下一跳節(jié)點的自適應選擇；優(yōu)化了下一跳節(jié)點選擇策略，通過概率值的大小判斷鄰居節(jié)點中性能最好的節(jié)點，以此作為下一跳，完成非聯(lián)通子網絡間的數(shù)據接力傳輸。

3) 與傳統(tǒng)算法的仿真對比，顯示了本文算法在投遞投遞率、投遞延遲、網絡負載率方面綜合提高了33%，實現(xiàn)分割網絡間的數(shù)據逐跳傳輸。