隨意式網路中建構具能源感知與維護機制的連通支配集之集中式演算法

Centralized Algorithms based on Energy-Aware and Maintained Mechanism for Constructing Connected Dominating Set in Ad Hoc Networks

陳堃維(Kun-Wei Chen)

指導教授 ： 林傳筆

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

摘要

在無線隨意式網路中，由於頻寬的資源、節點處理能力與電池功率有限等問題，且節點具有移動的特性而造成網路拓樸動態地改變。為了解決上述的問題，而以連通支配集 (Connected Dominating Set, CDS)作為繞送的方式被認為適合運用在無線隨意式網路中，利用CDS當作一個虛擬骨幹(Virtual Backbone)來進行資料傳輸，可以有效減少冗餘的訊息傳輸與電力消耗以及迅速地適應網路拓樸的改變。因此在本論文中，我們提出Maxsufferage Selection CDS (MaxS-CDS)及Maximum Energy-Aware CDS (MEA-CDS)兩種建構CDS的演算法，其中MaxS-CDS演算法之目的在於減少節點之間的訊息傳輸、頻寬浪費及電力消耗，來達到省電效果。然而MEA-CDS演算法之目的在於建構CDS時，考慮節點的電力條件來增長CDS的生命週期。除此之外，本論文加入了Recovery程序，將電力較低的CDS gateway找出其他節點來替換，達到增長CDS生命週期的效果。然而將本論文所提出的兩種演算法與其他演算法進行實驗比較後，實驗結果呈現MaxS-CDS演算法能獲得較小的CDS gateway數量，而MEA-CDS演算法能獲得較長的CDS生命週期。

關鍵字

虛擬骨幹 ； 連通支配集 ； 無線隨意式網路 ； 能源感知 ； 復原

並列摘要

There exist some problems in wireless ad hoc networks, such as the limitations of bandwidth, the processing capability of nodes, and the battery power. This is because the network topology may dramatically change due to node mobility in wireless ad hoc networks. To solve the above problems, the design of routing algorithms based on connected dominating set (CDS) has been recognized as a suitable approach for routing in ad hoc networks, because the CDS as a virtual backbone to relay data not only can reduce redundant message and power consumption but also can adapt to the rapid change of network topology. Therefore, in this paper, we propose two novel CDS algorithms, called Maxsufferage Selection CDS (MaxS-CDS) and Maximum Energy-Aware CDS (MEA-CDS). The purpose of MaxS-CDS algorithm is to reduce the transmission time of messages between nodes, waste of bandwidth and power consumption. However, the lifetime of CDS is not considered in MaxS-CDS algorithm. Therefore, the MEA-CDS algorithm is to improve lifetime of CDS by considering powers of nodes when constructing CDS. Furthermore, we also propose Recovery Procedure to replace lower power of node and improve lifetime of CDS. , The proposed two algorithms are simulated and compared with other algorithms. The simulation results show that MaxS-CDS algorithm obtains the smaller size of CDS than others algorithms and MEA-CDS algorithm obtains the longer lifetime of CDS than others algorithms.

並列關鍵字

Virtual Backbone ； Connected Dominating Set(CDS) ； Wireless Ad Hoc Networks ； Energy-Aware ； Recovery

參考文獻

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

[2] B. Das and V. Bhargavan, “Routing in Ad-Hoc Networks Using Minimum Connected Dominating Sets,” Proceedings of IEEE International Conference on Communications, 1997, pp. 376-380.

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

[4] F. Dai and J. Wu, “On constructing k-connected k-dominating set in wireless networks,” Proceedings of the 19th IEEE International Parallel and Distributed Processing Symposium, 2005, pp. 81a-81a.

[5] P. Fly and N. Meghanathan, "Predicted Link Expiration Time Based Connected Dominating Sets for Mobile Ad hoc Networks," International Journal on Computer Science and Engineering, 2010, Vol. 2, No. 6, pp. 2096-2103.