臺灣博碩士論文加值系統

在無線隨意式網路中，由於頻寬的資源、節點處理能力與電池功率有限等問題，且節點具有移動的特性而造成網路拓樸動態地改變。為了解決上述的問題，而以連通支配集 (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.

主目錄
摘要 I
Abstract II
誌謝 III
第 1 章 緒論 1
1.1. 研究背景 1
1.2. 無線隨意式網路介紹 2
1.3. 研究動機與目的 3
1.4. 論文架構 4
第 2 章 相關研究 6
2.1. 路由協定 6
2.1.1. 主動式路由 6
2.1.2. 回應式路由 7
2.1.3. 階層式路由 7
2.2. 建構Connected Dominating Set的各種方法 10
2.2.1. 集中式演算法 10
2.2.2. 分散式演算法 12
2.2.3. 以電力條件建構CDS的演算法 15
第 3 章 研究方法 18
3.1. 數學符號和名詞定義 19
3.2. MaxS-CDS演算法 20
3.2.1. Sufferage CDS Selection程序 21
3.2.2. Remark程序 23
3.3. MEA-CDS演算法 25
3.3.1. Maximum Energy-Aware CDS Selection程序 26
3.3.2. Recovery程序 28
第 4 章 實例說明 30
4.1. MaxS-CDS演算法之實例說明 31
4.2. MEA-CDS演算法之實例說明 38
第 5 章 實驗模擬與分析 50
5.1. 模擬實驗環境與步驟 50
5.2. 實驗結果與分析 52
5.2.1. 實驗一：CDS gateway數量的比較 53
5.2.2. 實驗二：CDS生命週期的比較 56
5.3. 實驗結論 64
第 6 章 結論與未來工作 65
參考文獻 67


表目錄
表格2-1 節點1支配的成員 9
表格2-2 節點1之繞送表格 9

圖目錄
圖2-1 無線Ad hoc網路的例子 9
圖3-1 Sufferage CDS Selection程序之演算法 23
圖3-2 Maximum Energy-Aware CDS Selection程序之演算法 27
圖4-1 各圖形實例的節點定義 30
圖4-2 MaxS-CDS初始網路圖形 31
圖4-3 MaxS-CDS第1次計算SV 32
圖4-4 MaxS-CDS第1次執行 33
圖4-5 MaxS-CDS第2次執行 33
圖4-6 MaxS-CDS第3次執行 34
圖4-7 MaxS-CDS第4次執行 35
圖4-8 MaxS-CDS第5次執行 36
圖4-9 MaxS-CDS第6次執行，建構CDS的數量為6個 36
圖4-10 節點16進行Remark程序 37
圖4-11 MaxS-CDS第7次執行，建構的CDS數量為5個 38
圖4-12 MEA-CDS初始網路圖形 39
圖4-13 MEA-CDS第1次執行 40
圖4-14 MEA-CDS第2次執行 40
圖4-15 MEA-CDS第3次執行 41
圖4-16 MEA-CDS第4次執行 42
圖4-17 MEA-CDS第5次執行 42
圖4-18 MEA-CDS第6次執行 43
圖4-19 MEA-CDS第7次執行 44
圖4-20 MEA-CDS第8次執行，建構的數量為8個 44
圖4-21 節點1將進行Recovery程序 45
圖4-22 節點1第1次計算2-hop內各節點的權重值 46
圖4-23 節點16加入Recovery Set 47
圖4-24 節點1第2次計算2-hop內各節點的權重值 48
圖4-25 節點13加入Recovery Set 48
圖4-26 完成Recovery程序之結果 49
圖5-1 各種演算法CDS gateway的數量(傳輸半徑為R=25m) 55
圖5-2 各種演算法CDS gateway的數量(傳輸半徑為R=40m) 56
圖5-3 各種演算法CDS的生命週期(傳輸半徑為R=25m, α=0.02) 59
圖5-4 各種演算法CDS的生命週期(傳輸半徑為R=25m, α=0.05) 59
圖5-5 各種演算法CDS的生命週期(傳輸半徑為R=40m, α=0.02) 60
圖5-6 各種演算法CDS的生命週期(傳輸半徑為R=40m, α=0.05) 61
圖5-7 各種演算法CDS的生命週期(傳輸半徑為R=25m, α=0.1) 62
圖5-8 各種演算法CDS的生命週期(傳輸半徑為R=25m, α=0.25) 62
圖5-9 各種演算法CDS的生命週期(傳輸半徑為R=40m, α=0.1) 63
圖5-10 各種演算法CDS的生命週期(傳輸半徑為R=40m, α=0.25) 63

[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.
[6]D. B. Johnson and D. A. Maltz, “The Dynamic Source Routing Protocol for Mobile Ad Hoc Networks,” Intemet-Draft, draft-ietf-manet-dsr-00.txt, 1998.
[7]H. Lim and C. Kim, "Flooding in Wireless Ad Hoc Networks," Computer Communications, 2001, Vol. 24, No. 3-4, pp. 353-363.
[8]S. Lee, B. Bhattacharjee, A. Srinivasan and S. Khuller, "Efficient and Resilient Backbones for Multihop Wireless Networks." IEEE Transactions on Mobile Computing, 2008, Vol. 7, No. 11, pp. 1349-1362.
[9]C. Markarian and F. N. Abu-Khzam, “A Degree-Based Heuristic for Strongly Connected Dominating-Absorbent Sets in Wireless Ad-Hoc Networks,” Proceedings of IEEE International Conference on Innovations in Information Technology, 2012, pp. 200-204.
[10]M. Maheswaran, S. Ali, H. J. Siegal, D. Hensgen, R. F. Freund, “Dynamic matching and scheduling of a class of independent tasks onto heterogeneous computing systems,” Proceedings of 8th IEEE Heterogeneous Computing Workshop, 1999, pp. 30-44.
[11]N. Meghanathan, “An Algorithm to Determine Minimum Velocity-based Stable Connected Dominating Sets for Ad hoc Networks,” Communications in Computer Science and Engineering, 2010, pp. 206-217.
[12]N. Meghanathan and A. Farago, "On the stability of paths, Steiner trees and connected dominating sets in mobile ad hoc networks," Ad Hoc Networks, 2008, Vol. 6, No. 5, pp. 744-769.
[13]N. Meghanathan and M. Terrell, "An Algorithm to Determine Stable Connected Dominating Sets for Mobile Ad hoc Networks using Strong Neighborhoods," International Journal of Combinatorial Optimization Problems and Informatics, 2012, Vol. 3, No. 2, pp. 79-92.
[14]S. Murthy and J. J. Garcia-Luna-Aceves, “A Routing Protocol for Packet Radio Networks,” Proceedings of the 1st Annual ACM International Conference on Mobile Computing and Networking, 1995, pp. 86-95.
[15]C. E. Perkins and P. Bhagwat, “Highly Dynamic Destination Sequenced Distance Vector Routing (DSDV) for Mobile Computers,” Proceedings of ACM Conference on Communications Architectures, 1994, Vol. 24, No. 4, pp.234-244.
[16]C. E. Perkins, and E. M. Royer, “Ad-hoc On-Demand Distance Vector Routing,” Proceedings of 2nd IEEE Workshop on Mobile Computing Systems and Applications, 1999, pp. 90-100.
[17]T. S. Rappaport, Wireless Communications: Principles & Practice, Prentice Hall, 2002.
[18]J. Z. Sun, “Mobile Ad Hoc Networking: An Essential Technology for Pervasive Computing,” Proceedings of IEEE International Conferences on Info-tech and Info-net, 2001.
[19]P. Sheu and Y. Lee, “On Calculating Stable Connected Dominating Sets Base on Battery Power for Mobile Ad Hoc Networks,” Proceedings of International symposium on Communications, 2003.
[20]Y. C. Tseng, S. Y. Ni, Y. S. Chen and J. P. Sheu, “The Broadcast Storm Problem in a Mobile Ad Hoc Network,” Proceedings of the 5th Annual ACM/IEEE International Conference on Mobile Computing and Networking, 1999, pp. 151-162.
[21]N. Velummylum and N. Meghanathan, "On the Utilization of ID-based Connected Dominating Sets for Mobile Ad hoc Networks," International Journal of Advanced Research in Computer Science, 2010, Vol. 1, No. 3, pp. 36-43.
[22]F. Wang, M. T. Thai and D. Z. Du, "On the Construction of 2-Connected Virtual Backbone in Wireless Networks," IEEE Transactions on Wireless Communications, 2009, Vol. 8, No. 3, pp. 1230-1237.
[23]J. Wu, "Extended Dominating-Set-Based Routing in Ad Hoc Wireless Networks with Unidirectional Links," IEEE Transactions on Parallel and Distributed Systems, 2002, Vol. 13, No. 9, pp. 866-881.
[24]J. Wu and H. Li, “On Calculating Connected Dominating Set for Efficient Routing in Ad Hoc Wireless Networks,” Proceedings of the 3rd International Workshop on Discrete Algorithms and Methods for Mobile Computing and Communications, 1999, pp. 7-14.
[25]J. Wu, D. Fai, M. Gao and I. Stojmenovic, "On Calculating Power-Aware Connected Dominating Sets for Efficient Routing in Ad Hoc Wireless Networks," IEEE Journal of Communications and Networks, 2002, Vol. 4, No. 1, pp. 59-70.
[26]C. Zheng, L. Yin and Y. Zhang, “Constructing r-Hop 2-Connected Dominating Sets for Fault-Tolerant Backbone in Wireless Sensor Networks, ” Proceedings of the 8th IEEE International Conferences on Wireless Communications, Networking and Mobile Computing, 2012, pp. 1-4.
[27]賈坤芳、江茂綸、陳俊榮，「利用區域演算法將ad hoc 無線網路下之Connected Dominating Set 最小化」，全國計算機會議，2005。
[28]林靖洋，隨意無線網路中虛擬骨幹的局部維護機制，碩士論文，國立中山大學電機工程學系，高雄，2013。
[29]陳俊榮，Ad Hoc無線網路中利用ID重置技術建構最小省電Connected Dominating Set的區域演算法，碩士論文，國立中興大學資訊科學研究所，臺中，2006。