移動隨意式網路中透過推派演算法建構最小化的連通支配集之分散式演算法

Decentralized Algorithm for Constructing Minimized Connected Dominating Sets by Nominate Algorithms in Mobile Ad-hoc Networks

陳澤宇(ZE-YU CHEN)

指導教授 ： 江茂綸

朝陽科技大學/資訊學院/資訊與通訊系/碩士(2019年)

摘要

移動隨意式網路(Mobile Ad-hoc NETwork, MANET)是一種動態網路拓撲，主要以移動節點透過封包轉發來實現訊息的交換。由於MANET缺乏物理的骨幹網路，因此，MANET在廣播通訊的過程中，容易造成頻寬浪費和訊息衝突等問題，導致路由降低性能並浪費節點的能量。所以，需要提出節點之間的有效路由演算法來解決上述的問題。因此，連通支配集(Connected Dominating Set, CDS)被提出做為MANET建構虛擬骨幹的方法之一。CDS的主要概念是減少集合中節點的路由搜尋空間，隨後便以CDS做為MANET的虛擬骨幹，以降低路由傳輸訊息所損耗的頻寬和能源，進而及增強網路的可擴展性。然而，由於移動節點的分佈不佳，過去所提出的CDS演算法無法在MANET中找到最小的CDS數量。因此，本論文提出一個分散式的Nominate-CDS(Nom-CDS)演算法，其概念為各節點選擇最具影響力的相鄰節點做為CDS的成員，接著再降低其CDS成員及確保CDS連通狀態，進而建構出近似最小的數量的CDS架構來降低頻寬的浪費。其實驗結果呈現所提出之Nom-CDS演算法能夠獲得較小的CDS數量。

關鍵字

路由演算法 ； 移動隨意式網路 ； 連通支配集 ； 虛擬骨幹

並列摘要

Mobile Ad-hoc NETwork (MANET) is a dynamic network topology and their messages are exchanged or forwarding by each mobile node. However, the broadcasting messages in a MANET waste a lot of bandwidth and cause packet collisions. As a result, the routing performance is reduced and the energy of the node is wasted. Therefore, an efficient routing algorithm between mobile nodes needs to be proposed to solve the above problem. Connected Dominating Set (CDS) is proposed to construct a virtual backbone for MANET. The main concept of CDS is to reduce the search space for the route to the mobile node in the set. Namely, the CDS can be invoked to reduce the bandwidth and energy consumed by routing messages. Then, the virtual backbone can avoid packet collisions and enhance the scalability of the network. However, the previous CDS algorithms cannot find the minimum number of CDS in MANET due to the random distribution of mobile nodes. Therefore, a decentralized Nominate-CDS (Nom-CDS) algorithm is proposed to solve above problems. The concept of Nom-CDS is that each node selects the most influential neighbor node as a member of the CDS, then prunes CDS and ensures the CDS connectivity state. Finally, the simulation results show that the Nom-CDS algorithm can obtain a smaller number of CDS than others.

並列關鍵字

Virtual Backbone ； Routing algorithm ； Mobile Ad-Hoc Network ； Connected Domination Set

參考文獻

[1] 林靖洋，“隨意無線網路中虛擬骨幹的局部維護機制”，碩士論文，國立中山大學電機工程學系，高雄，2013。

[2] 陳俊榮，“Ad Hoc無線網路中利用ID重置技術建構最小省電Connected Dominating Set的區域演算法”，碩士論文，國立中興大學資訊科學研究所，臺中，2006。

[3] M. Abolhasan, T. Wysocki, and E. Dutkiewicz, “A Review of Routing Protocols for Mobile Ad hoc Networks,” Ad hoc networks, January 2004, Vol. 2, No. 1, pp. 1-22.

[4] O. Chaturvedi, P. Kaur, N. Ahuja, and T. Prakash, “Improved algorithms for construction of connected dominating set in MANETs,” Cloud System and Big Data Engineering (Confluence), July 2016, pp. 559-564.

[5] F. Dai and J. Wu, “Distributed Dominant Pruning in Ad Hoc Wireless Networks,” Proceedings of IEEE International Conference on Communications, June 2003, pp. 353-357.