行動隨意網路下有距離認知的廣播方法

Abstract

在無線隨意網路中(MANETs), 廣播機制是一個常見的功能，用以提供各種網路服務，例如：路由路徑搜尋、資源搜索…等等。然而，沒有適當的控制機制─即所謂的氾濫廣播法，會導致嚴重的重送、競爭以及碰撞問題。這些問題被定義為「廣播風暴問題」，已經有許多研究提出了解決的方法，但是大部分的方法在網路涵蓋能力(Reachability)以及節省重送效能(Saved Rebroadcast)上無法取得平衡。在計數方法(counter-based scheme)中，每個無線節點根據鄰近區域的節點密度決定是否重送，然而，這個方法並沒有將每個重送點之間的相對距離的觀念加入考慮，我們提出了幾個解決問題的方法，DISCOUNT以及DIS_RAD (DIStinct RAD)演算法，前者將技術方法以及距離感測方法作了一個良好的混合，將距離觀念加入計數方法中，我們演算法的基本觀念是，外圈的應該有較高的重送機率，因為他們有較好的額外覆蓋面積(EAC)，在此演算法中，我們利用距離門檻 (distance threshold)來區別內圈點及外圈點，並採用不同的隨機延遲時間(RAD)，並針對內圈點及外圈點此用不同的隨機延遲時間，使得外圈點有較短的延遲時間，基於此種改變，我們推導出了內圈點及外圈點兩種不同的重送機率，分析的結果顯示我們的演算法的確可對外圈點提供較高的重送機率，內圈點提供較低的重送機率。模擬結果描述了DIS_RAD的確會提供比技術方法有好的多的效能，此結果也與我們的機率分析模型箱符合。最重要的是，我們的方法不管在任何不同的網路密度皆可提供良好的網路涵蓋能力以及節省重送效能。

In mobile ad hoc networks (MANETs), broadcasting is a common operation for providing network functions, such as route discovery and source paging. However, an uncontrolled broadcast, which is also called blind flooding, is inefficient and may lead to heavy redundancies, contentions and collisions, and is commonly referred to as a “broadcast storm” [1]. Although this problem has been addressed extensively, most studies suffer with respect to balance between coverage performance and rebroadcasting efficiency. In a counter-based scheme, a mobile node determines the rebroadcast probability based on the node density in its neighborhood, but does not include the distance concepts which helps improve the Expected Additional Coverage (EAC) [1]. This investigation proposes several algorithms to solve broadcast storm problem. The DISCOUNT scheme combines both DIStance-based and COUNTter-based schemes. The DIS_RAD distinguishes different Random Assessment Delays (RAD) from border nodes to interior ones. The DISCOUNT-RS further improve the performance of the mentioned algorithms. The basic idea of these algorithms is that give nodes closer to the border should have a higher rebroadcast probability since they create better Expected Additional Coverage (EAC) values. Here, a distance threshold is adopted to distinguish between interior and border nodes. Two distinct RADs are applied to the border and interior nodes, with the border nodes having shorter RADs than the interior nodes. Based on this change, the two rebroadcast probabilities are derived for the nodes located at the border annulus and those located at the interior circle. The analytical results indicate that the proposed scheme indeed provides a higher rebroadcast probability for border nodes and a lower rebroadcast probability for interior nodes compared with the counter-based scheme. The simulation results demonstrate that the proposed “DIS_RAD” scheme works much better than the counter-based scheme. The probability analysis model also confirms the validity of the simulation results. The most important, the proposed scheme can keep good balance between reachability and rebroadcast efficiency in various network densities. Therefore, the dynamic adjust counter threshold according to network densities is not necessary.