劉鑒葳，李文藻

（成都信息工程大學 通信工程學院，四川 成都 610225）

基于社會網(wǎng)絡洪泛算法的消息隊列轉(zhuǎn)發(fā)策略設計

劉鑒葳，李文藻

（成都信息工程大學 通信工程學院，四川 成都 610225）

隨著智慧城市的發(fā)展，移動智能終端的普及，社會網(wǎng)絡成為研究人員熱議的話題。由于洪泛算法在網(wǎng)絡投遞率、網(wǎng)絡延遲方面有著較為突出的表現(xiàn)，文章主要基于社會網(wǎng)絡的洪泛算法，設計了MUOB的消息隊列轉(zhuǎn)發(fā)策略。通過實驗結(jié)果表明MUOB轉(zhuǎn)發(fā)策略在網(wǎng)絡投遞率、網(wǎng)絡延遲方面優(yōu)于傳統(tǒng)的隨機轉(zhuǎn)發(fā)策略，先進先出轉(zhuǎn)發(fā)策略以及最近的MinHop轉(zhuǎn)發(fā)策略。

社會網(wǎng)絡；洪泛算法；轉(zhuǎn)發(fā)策略；緩存空間

一方面，智慧城市概念的興起，使得物聯(lián)網(wǎng)、移動智能終端、云計算發(fā)展迅速，社會網(wǎng)絡漸漸走入研究人員的視野。另一方面，行人節(jié)點在社會網(wǎng)絡中是產(chǎn)生數(shù)據(jù)，消費數(shù)據(jù)的重要主體[1]。洪泛算法相較于網(wǎng)絡中其他算法擁有高的網(wǎng)絡投遞率，以及低網(wǎng)絡延遲的特性，但其消息的轉(zhuǎn)發(fā)策略絕大部分并沒有基于社會網(wǎng)絡中的行人特征。雖然近年來出現(xiàn)了MinHop轉(zhuǎn)發(fā)策略，考慮了社會網(wǎng)絡中的行人社交屬性等特征，并比基于傳統(tǒng)轉(zhuǎn)發(fā)策略的網(wǎng)絡性能更好，但其策略偏于簡單，并未充分發(fā)揮洪泛算法的網(wǎng)絡性能。因此本文重新設計了一種節(jié)點緩沖區(qū)消息隊列的排序策略，叫作最大化利用緩存空間（Maximize Utilization of Buffer，MUOB），并與洪泛算法中傳統(tǒng)的隨機轉(zhuǎn)發(fā)策略、先進先出（First In First Out，F(xiàn)IFO）以及最近的MinHop的轉(zhuǎn)發(fā)策略進行比較。實驗結(jié)果表明，MUOB在網(wǎng)絡投遞率、網(wǎng)絡延遲方面優(yōu)于其他3個轉(zhuǎn)發(fā)策略。

1 傳統(tǒng)消息隊列轉(zhuǎn)發(fā)策略以及MinHop轉(zhuǎn)發(fā)策略

目前消息在節(jié)點中的傳統(tǒng)排序方式有：Random轉(zhuǎn)發(fā)策略，即節(jié)點相遇后消息隨機進行投遞。FIFO轉(zhuǎn)發(fā)策略是指節(jié)點緩存區(qū)的消息按進入緩存區(qū)的時間先后進行排序，依次投遞。MinHop轉(zhuǎn)發(fā)策略是近年由QAISAR等[2]提出，該轉(zhuǎn)發(fā)策略基于行人社交屬性構(gòu)建的社會網(wǎng)絡，并模擬城市環(huán)境進行實驗分析。MinHop轉(zhuǎn)發(fā)策略將節(jié)點緩存區(qū)的消息按照轉(zhuǎn)發(fā)次數(shù)進行排序，當節(jié)點相遇時，轉(zhuǎn)發(fā)次數(shù)少的消息優(yōu)先進行投遞。其實驗結(jié)果顯示MinHop比傳統(tǒng)的FIFO，Random轉(zhuǎn)發(fā)策略的網(wǎng)絡性能更好。

2 MUOB轉(zhuǎn)發(fā)策略設計

2.1 MUOB轉(zhuǎn)發(fā)策略的目標

MUOB的核心目標是提出一種對節(jié)點緩存進行優(yōu)化的策略，減少節(jié)點的緩存中存在緩存占比大，且剩余存活時間（Time To Live，TTL）小的消息投遞的可能。因為若不對此類消息優(yōu)先級進行控制，會增大網(wǎng)絡負載，并且存活時間不長易造成網(wǎng)絡投遞率低，這浪費了節(jié)點本身的緩存。MUOB旨在找到一個參數(shù)，來衡量占用節(jié)點緩存小、TTL大的消息，并將節(jié)點緩存區(qū)的消息按照此參數(shù)排序且優(yōu)先轉(zhuǎn)發(fā)。通過該策略就可以充分地利用節(jié)點緩存，并充分發(fā)揮洪泛算法的網(wǎng)絡性能。

2.2 MUOB緩存區(qū)算法設計

MUOB提出了一個新參數(shù)：消息剩余極限跳數(shù)因子α，來衡量節(jié)點中消息緩存占用量與TTL。α代表了一個消息在未來可能是實現(xiàn)的極限多的跳數(shù)。

簡單來說，假設一個節(jié)點中有n個消息，且大小為{Sn|n∈Z*}，Z*為正整數(shù)。投遞第i（0≤i≤n）個消息所需要的時間Ti=Si/Ts，Ts表示消息投遞速率。從而就可以得到第i個消息的剩余極限跳數(shù)因子αi=TTLi/Ti，TTLi代表第i個消息的TTL。

不難看出α綜合考慮了消息的緩存占用大小，以及消息的TTL。α值越大，意味著未來實現(xiàn)多跳的機會越多，所以將α值大的消息進行優(yōu)先投遞，理論可以實現(xiàn)對節(jié)點緩存區(qū)的優(yōu)化，讓緩存占比小，且TTL長的消息優(yōu)先投遞。因此MUOB轉(zhuǎn)發(fā)策略可以極大利用節(jié)點緩存空間，充分發(fā)揮洪泛算法的網(wǎng)絡性能，提高網(wǎng)絡投遞率，降低網(wǎng)絡延遲。

3 仿真及實驗結(jié)果

此次仿真采用ONE仿真平臺，使用Helsinki地圖，節(jié)點移動模型使用WorkingDayMovement，并作出如下的關鍵配置參數(shù)：消息的TTL為400 s，行人節(jié)點平均分為5組，共計175個。設置行人節(jié)點的移動速度為0.5～1.5 m/s，工作日時長28 800 s，仿真時間432 000 s。整個網(wǎng)絡中所有節(jié)點均選用藍牙接口，投遞距離小于10 m，并設置消息投遞速率為250 kb/s。

此次仿真選擇Random，F(xiàn)IFO，MinHop，MUOB 4種消息隊列轉(zhuǎn)發(fā)策略，并設置不同節(jié)點緩存比較4種策略的投遞率、延遲情況，網(wǎng)絡投遞率比較結(jié)果如表1所示。

其結(jié)果顯示MUOB在網(wǎng)絡投遞率上具有較好的表現(xiàn)，在不同節(jié)點緩存區(qū)的大小下均高于其他3個轉(zhuǎn)發(fā)策略，MUOB在網(wǎng)絡投遞率上比MinHop高了2%～6%。

網(wǎng)絡平均延遲取整情況如表2所示，不難看出MUOB轉(zhuǎn)發(fā)策略相較于其他3個轉(zhuǎn)發(fā)策略的網(wǎng)絡延遲小，且平均比MinHop小657s，平均降低了5%的網(wǎng)絡延遲。實驗結(jié)果總體表明MUOB轉(zhuǎn)發(fā)策略對洪泛算法的網(wǎng)絡性能有明顯的提升。

綜上所述，洪泛算法的多副本策略對節(jié)點緩存區(qū)大小來說是個嚴峻的挑戰(zhàn)，MUOB是對節(jié)點緩存的一種優(yōu)化策略。多次的實驗結(jié)果表明，MUOB實現(xiàn)了對節(jié)點緩存優(yōu)化的目標，相較MinHop，F(xiàn)IFO，Random這3種消息隊列轉(zhuǎn)發(fā)策略，MUOB進一步提升了洪泛算法在社會網(wǎng)絡中的網(wǎng)絡性能。

表1 4種消息列隊轉(zhuǎn)發(fā)策略的網(wǎng)絡投遞率的仿真結(jié)果

表2 4種消息列隊轉(zhuǎn)發(fā)策略的網(wǎng)絡延遲的仿真結(jié)果 （單位：s）

[1]LI W Z，LIN F，WU X，ZHOU J L.Valuable First Forwarding（VFF）Transmission Strategy for Epidemic Routing in Urban Environments[J]. Global Journal of Computer Science and Technology，2017（17）：1-10.

[2]AYUB Q，RASHID S，ZAHID M S M.MinHop（MH）Transmission strategy to optimized performance of epidemic routing protocol[J].Global Journal of Computer Science and Technology，2011（9）：35-39.

Design of message queue forwarding strategy based on the flood algorithm in social network

Liu Jianwei, Li Wenzao
（Communication Engineering College of Chengdu University of Information Technology, Chengdu 610225, China）

With the development of smart city and the popularity of mobile smart terminals, social networks has becoming a hot topic in such research area. Because the flood algorithm has a more prominent performance in terms of network delivery ratio and network latency average, this paper designs a message queue forwarding strategy of MUOB based on the flood algorithm in social network.The experimental results show that the MUOB forwarding strategy is superior to the traditional random forwarding strategy, the FIFO forwarding strategy and the recent forwarding strategy based on the MinHop count in terms of network delivery ratio and network latency average.

social network; flood algorithm; forwarding strategy; buffer space

成都信息工程大學通信工程學院院教改項目；項目編號：YJG2017003。

劉鑒葳（1991— ），男，四川成都人，碩士研究生；研究方向：無線傳感器網(wǎng)絡。