Reliable Cluster Construction and QoS-Constrained Routing Assignment in Wireless Mobile Ad Hoc Networks
Date Issued
2005
Date
2005
Author(s)
Lin, Ming-Yuan
DOI
en-US
Abstract
With the development of Mobile Ad Hoc Networks (MENETs), providing ubiquitous communications and a convenient framework for applications requires network management to guarantee that the network topology is reliable and efficient. However, the mobility of wireless devices, wireless communication limitations, frequent route breakdowns and unpredictable topology changes make the network management complex and difficult. In a distributed environment, how to construct a network topology and QoS constrained routing assignment with high stability has thus become a popular issue.
In this thesis, we attempt to solve the problem of reliable cluster construction and the QoS constrained routing assignment. We assume that there exists a central decision system, such as a Geographical Positioning System (GPS), to monitor the entire wireless network and disseminate information. By using a mathematical technique, we model the problem as an integer optimization model, where the objective function is to maximize the minimum link duration of the constructed network topology and routing assignment. Like conventional clustering problems, we first group devices into different clusters and determine the clusterhead/cluster member relationship. Based on the constructed cluster topology, we jointly determine the routing assignment with QoS constraints, such as nodal capacity and end-to-end delay. The difference between our proposed algorithm and other algorithms is that for a heavily-loaded node, we aggregate the traffic demands of all O-D pairs and reroute some congested routing paths to achieve load balance and optimize the utilization and stability of the network.
Because of the difficulty and complexity of the optimization problem, we adopt Lagrangean Relaxation and the subgradient method. By applying the latter method’s properties and getting a primal heuristic, we can solve the complicated optimization problem efficiently and improve the solution quality iteration by iteration.
Subjects
無線移動網路
叢聚拓樸
網路規劃
考量服務品質之路由規劃
穩定性
最佳化
拉格蘭日鬆弛法
數學規劃
Mobile Ad Hoc Network
Reliable Cluster Construction
QoS Constrained Routing Assignment
Reliability
Mathematical Programming
Optimization
Lagrangean Relaxation
Type
other
File(s)![Thumbnail Image]()
Loading...
Name
ntu-94-R92725034-1.pdf
Size
23.31 KB
Format
Adobe PDF
Checksum
(MD5):eff2f6fa98f2c532cda94882be99a45b