基于社會網絡洪泛算法的消息隊列轉發策略設計

劉鑒葳，李文藻

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

基于社會網絡洪泛算法的消息隊列轉發策略設計

劉鑒葳，李文藻

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

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

社會網絡；洪泛算法；轉發策略；緩存空間

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

1 傳統消息隊列轉發策略以及MinHop轉發策略

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

2 MUOB轉發策略設計

2.1 MUOB轉發策略的目標

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

2.2 MUOB緩存區算法設計

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

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

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

3 仿真及實驗結果

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

此次仿真選擇Random，FIFO，MinHop，MUOB 4種消息隊列轉發策略，并設置不同節點緩存比較4種策略的投遞率、延遲情況，網絡投遞率比較結果如表1所示。

其結果顯示MUOB在網絡投遞率上具有較好的表現，在不同節點緩存區的大小下均高于其他3個轉發策略，MUOB在網絡投遞率上比MinHop高了2%～6%。

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

綜上所述，洪泛算法的多副本策略對節點緩存區大小來說是個嚴峻的挑戰，MUOB是對節點緩存的一種優化策略。多次的實驗結果表明，MUOB實現了對節點緩存優化的目標，相較MinHop，FIFO，Random這3種消息隊列轉發策略，MUOB進一步提升了洪泛算法在社會網絡中的網絡性能。

表1 4種消息列隊轉發策略的網絡投遞率的仿真結果

表2 4種消息列隊轉發策略的網絡延遲的仿真結果 （單位：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— ），男，四川成都人，碩士研究生；研究方向：無線傳感器網絡。