移動隨意網路下植基於基因演算法之能源考量QoS群播選徑

Abstract

求解兩個或多個限制參數（Multi-constraints）的QoS 群 播 路 由 問 題 ， 已 被 實 證 是 屬 於 NP-complete（Non-deterministic Polynomial）問題，無法在多項式時間內求得最佳解。本論文提出在移動隨意網路下植基於基 因 演 算 法 之 能 源 考 量 QoS 群 播 選 徑 (Energy-Aware QoS Multicast Routing Protocol，EAQMRP)機制來解決此問題，同時考量傳播延遲和節點電量作為QoS群播選徑 問 題 中 目 標 函 數 之 參 數 ， 並 且 提 出 一 種 新 式 的 ST（Sequence and Topology）編碼方式，使基因演算法的操作可以快速收斂選出既省電又有效率和強韌性的群播繞送路徑。To solve more than one QoS constraints often make the QoS routing NP-complete problem. Traditional multicast routing algorithms cannot solve the Qos routing problem satisfactorily. In other words, to solve more than one QoS constraints often make the QoS multicast routing NP-complete problem. The term NP denotes non- deterministic polynomial. To resolve this problem, we introduce a mechanism of “Energy-Aware QoS Multicast Routing Protocol based on Genetic Algorithm for the Mobile Ad Hoc Networks”, not only considering both the propagation delay and Residual Battery Energy (RBE) as metrics of objective function, but also proposed a new Sequence and Topology（ST） encoding. The ultimate goal of our algorithm is to prolong lifetime of multicast service by balancing battery energy of nodes in a multicast tree. We proposed a novel ST encoding and energy-aware mutation operator are different from traditional one. It is also an efficient and robust algorithm for multicast route selection.