An evolutionary programming algorithm for finding constrained optimal disjoint paths for multihop communication networks. (20th July 2010)

• Record Type: Journal Article
• Authors: Bhanja, Urmila; Roy, Rajarshi; Mahapatra, Sudipta
• Is Part Of: International journal of metaheuristics. Volume 1:Number 2(2010)
• Page Start: 132
• Page End: 155
• Publication Date: 2010-07-20
• Subjects: evolutionary programming algorithms -- disjoint paths -- constrained optimisation -- fitness functions -- mean execution time -- hop count bound -- NP hard problem -- QoS constraints -- quality of service -- dynamic topology -- metaheuristics -- fitness deviation -- bandwidth constraints -- multimedia delivery -- telecommunications networks; Heuristic algorithms -- Periodicals; 006.3105
• Languages: English
• ISSNs: 1755-2176

Abstract

We present an evolutionary programming algorithm (EP) for finding hop count and bandwidth constrained cost optimal disjoint paths in multihop communication networks. In general, multi-constrained path selection is an NP complete problem. Our proposed algorithm can be used for real-time online network applications, which can initiate and process a number of calls simultaneously on disjoint paths, without overloading the network. This algorithm also requires a small memory space and low execution time. The proposed algorithm, which maintains a balance between finding an optimal shortest path and CPU mean execution time, also generates parallel suboptimal paths during the process of generating the best path. One of these suboptimal paths can be used as a backup path if it is link disjoint with all the primary paths (best paths) of the concurrent requests. Thus, the proposed algorithm provides a limited degree of reliability for routing of packets as well.