臺灣博碩士論文加值系統

移動式隨意網路由許多自主移動的節點所組成，節點之間以無線媒介通訊。此網路架構不需仰賴已存的基礎建設，而網路拓樸會隨著節點的移動而持續變化。另一項重要的特性即為節點的電力資源有限，能量耗損會影響網路壽命長短，因此成為一項重要的效能衡量指標。

　　群播為移動式隨意網路中許多應用的基本運作機制，這些應用大部份都強調資訊傳輸的延遲限制，因此需要一個低延遲的群播演算法來滿足其限制，然而在設計的過程中同時考慮上述議題包括低能耗和節點移動性，會使問題變得十分複雜。

　　本論文主要研究在移動式隨意網路中多群組進行群播時，如何進行路由以及節點傳輸時間的排程問題。我們將此問題設計成一個數學模型，目標為最小化群播的延遲時間，同時我們也將群播產生之能耗限制在某個合理的範圍並且避免傳輸時會產生的資料碰撞，此碰撞情形會造成能量消耗。最後我們提出以拉格蘭日鬆弛法為基礎的演算法來解決此問題。我們設計一系列的實驗以測試演算法的表現，實驗結果顯示此演算法在多種網路情境下均能提供低延遲以及節能的傳輸排程。

A Mobile Ad Hoc Network (MANET) consists of a set of mobile nodes which communicate over the wireless medium. The network topology, which does not relay on any pre-existing infrastructure, changes rapidly due to the mobility of nodes. Another property of such networks is that the battery capability of nodes is limited. As a result, energy-efficiency becomes an important performance measure since it directly affects the network lifetime.
In MANET, multicasting is a fundamental operation to a wide range of applications which impose end-to-end latency constraints of transmissions. Designing a low-latency multicast protocol which satisfies these constraints is crucial important. However, it becomes a challenging task while addressing the critical issues of energy-efficiency and mobility at the same time.
In this thesis, we focus on the problem of routing and scheduling the transmission time of nodes for multi-group multicasting in MANET. We formulate the problem as a linear integer programming problem, in which the objective is to minimize the latency of multicasting. In addition, the formulation ensures the energy consumption within a reasonable range and avoids possible collisions of transmission which consume a large amount of valuable energy resources. A set of heuristic algorithms based on Lagrangean relaxation method is proposed to solve this problem. We conduct a series of experiment designed from the perspective of design and operation both. Experimental studies indicate that our algorithm has good performance and high practicability under various network conditions.

謝詞 I
論文摘要 III
THESIS ABSTRACT V
TABLE OF CONTENT VII
LIST OF TABLES IX
LIST OF FIGURES XI
CHAPTER 1 INTRODUCTION 1
1.1 BACKGROUND 1
1.2 MOTIVATION 4
1.3 LITERATURE SURVEY 6
1.3.1 Multicasting in Ad Hoc Networks 6
1.3.2 Scheduling of Broadcasting 11
1.3.3 Mobility Model 14
1.4 PROPOSED APPROACH 19
1.5 THESIS ORGANIZATION 19
CHAPTER 2 PROBLEM FORMULATION 21
2.1 PROBLEM DESCRIPTION 21
2.2 PROBLEM NOTATION 31
CHAPTER 3 SOLUTION APPROACH 43
3.1 INTRODUCTION TO LAGRANGEAN RELAXATION METHOD 43
3.2 LAGRANGEAN RELAXATION 46
3.2.1 Subproblem 1 49
3.2.2 Subproblem 2 49
3.2.3 Subproblem 3 51
3.2.4 Subproblem 4 52
3.2.5 Subproblem 5 53
3.2.6 Subproblem 6 54
3.2.7 Subproblem 7 54
3.2.8 Subproblem 8 57
3.3 THE DUAL PROBLEM AND THE SUBGRADIENT METHOD 58
CHAPTER 4 GETTING PRIMAL FEASIBLE SOLUTION 59
4.1 HEURISTIC FOR ROUTING POLICY 60
4.2 HEURISTIC FOR CALCULATING MAXIMAL TRANSMISSION TIME 61
4.3 HEURISTIC FOR SCHEDULING POLICY 64
4.4 HEURISTIC FOR SAVING ENERGY CONSUMPTION 66
4.5 LAGRANGEAN RELAXATION BASED ALGORITHM 67
CHAPTER 5 COMPUTATIONAL EXPERIMENTS 69
5.1 EXPERIMENT ENVIRONMENT 69
5.2 SIMPLE ALGORITHM FOR COMPARISON AND PERFORMANCE METRICS 70
5.3 EXPERIMENT SCENARIO 71
5.3.1 Static Network with Different Number of Nodes 71
5.3.2 Static Network with Different Number of Source Nodes 74
5.3.3 Dynamic Network with Different Density of Destination Nodes 75
5.3.4 Static Network with Different Transmission Radius 78
5.3.5 Dynamic Network with Different Transmission Radius 81
5.3.6 Summary 83
5.4 IMPLEMENTATION IN LONG-TERM OPERATION 84
5.4.1 A Scenario of Constant Speed during a Phase 87
5.4.2 A Scenario of Variable Speed during a Phase 98
CHAPTER 6 CONCLUSION 113
6.1 SUMMARY 113
6.2 FUTURE WORK 114
REFERENCES 115

[1]L. Chan and W. Heinzelman, “A Survey of Routing Protocols that Support QoS in Mobile Ad Hoc Networks,” IEEE Network, Vol. 21, No. 6, pp. 30-38, November-December 2007.
[2]C. T. Chou, J. Qadir, and J. G. Lim, “Advances and Challenges with Data broadcasting in Wireless Mesh Networks,” IEEE Communication Magazine, Vol. 45, No. 11, pp. 78-85, November 2007.
[3]X. Chen and J. Wu, “Multicasting Techniques in Mobile Ad Hoc Networks,” in The Handbook of Ad Hoc Wireless Networks. Boca Raton, CRC Press, pp. 35-50, 2003.
[4]H. Y. Youn, C. Yu, B. Lee, and S. Moh, “Energy Efficient Multicast in Ad Hoc Networks,” in The Handbook of Ad Hoc Wireless Networks . Boca Raton, CRC Press, pp. 374-385, 2003.
[5]J. E. Wieselthier, G.-D. Nguyen, and A. Ephremides, “Energy-Efficient Broadcast and Multicast Trees in Wireless Networks,” Mobile Network and Applications, Vol. 7, No. 6, pp. 481-492, December 2002.
[6]N. Rahnavard, B. N. Vellambi, F. Fekri, “Distributed Protocols for Finding Low-Cost Broadcast and Multicast Trees in Wireless Networks,” Proc. IEEE SECON’08, pp. 551-559, June 2008.
[7]H. Liu, X. Jia, P.-J. Wan, X. Liu, and F. F. Yao, “A Distributed and Efficient Flooding Scheme Using 1-Hop Information in Mobile Ad Hoc Networks,” IEEE Transactions on Parallel and Distributed Systems, Vol. 18, No. 5, pp. 658-671, May 2007.
[8]B. Williams and T. Camp, “Comparison of Broadcasting Techniques for Mobile Ad Hoc Networks,” Proc. 3rd ACM international symposium on Mobile ad hoc networking & computing, pp. 194-205, 2002.
[9]J.-P. Sheu, P.-K. Hung, and C.-S. Hsu, “Scheduling of broadcasts in Multihop Wireless Networks,” in The Handbook of Ad Hoc Wireless Network. Boca Raton, CRC Press, pp. 465-477, 2003.
[10]R. Gandhi, A. Mishra, and S. Parthasarathy, “Minimizing Broadcast Latency and Redundancy in Ad Hoc Networks,” IEEE/ACM Transactions on Networking, Vol. 16, No. 4, pp. 840-851, August 2008.
[11]A. A. Agashe and S. K. Bodhe, “Performance Evaluation of Mobility Models for Wireless Ad Hoc Networks,” Proc. ICETET’08, pp. 172-175, July 2008.
[12]T. Camp, J. Boleng, and V. Davies, “A Survey of Mobility Models for Ad Hoc Network Research,” Wireless Communications and Mobile Computing, Vol. 2, No. 5, pp. 483-502, 2002.
[13]W. Lou and J. Wu, “Toward Broadcast Reliability in Mobile Ad Hoc Networks with Double Coverage,” IEEE Transactions on Mobile Computing, Vol. 6, No. 2, February 2007.
[14]S.-J. Lee, W. Su, and M. Gerla, “On-Demand Multicast Routing Protocol in Multihop Wireless Mobile Networks,” Mobile Network and Applications, Vol. 7, No. 6, pp. 441-453, 2002.
[15]M. L. Fisher, “The Lagrangean Relaxation Method for Solving Integer Programming Problems,” Management Science, Vol. 27, No. 1, pp. 10-21, January 1981.
[16]A. M. Geoffrion, “Lagrangean Relaxation and its Use in Integer Programming,” Mathematical Programming Study, Vol. 2, pp. 82-114, 1974.
[17]M. Held, P. Wolfe, and H. P. Crowder, “Validation of Subgradient Optimization,” Mathematical Programming, Vol. 6, pp. 62-88, 1974.