Cognitive Shortest Path Tree Restoration (CSPTR) for MANET Using Cost-Sensitivity Analysis

Huan CHEN  Bo-Chao CHENG  Po-Kai TSENG  

IEICE TRANSACTIONS on Communications   Vol.E92-B   No.3   pp.717-727
Publication Date: 2009/03/01
Online ISSN: 1745-1345
DOI: 10.1587/transcom.E92.B.717
Print ISSN: 0916-8516
Type of Manuscript: Special Section PAPER (Special Section on Ad Hoc and Mesh Networking for Next Generation Access Systems)
OSPF,  MANET,  SPT,  restoration,  sensitivity analysis,  

Full Text: PDF(565.8KB)>>
Buy this Article

With quick topology changes due to mobile node movement or signal fading in MANET environments, conventional routing restoration processes are costly to implement and may incur high flooding of network traffic overhead and long routing path latency. Adopting the traditional shortest path tree (SPT) recomputation and restoration schemes used in Internet routing protocols will not work effectively for MANET. An object of the next generation SPT restoration system is to provide a cost-effective solution using an adaptive learning control system, wherein the SPT restoration engine is able to skip over the heavy SPT computation. We proposed a novel SPT restoration scheme, called Cognitive Shortest Path Tree Restoration (CSPTR). CSPTR is designed based on the Network Simplex Method (NSM) and Sensitivity Analysis (SA) techniques to provide a comprehensive and low-cost link failure healing process. NSM is used to derive the shortest paths for each node, while the use of SA can greatly reduce the effort of unnecessary recomputation of the SPT when network topology changes. In practice, a SA range table is used to enable the learning capability of CSPTR. The performance of computing and communication overheads are compared with other two well-known schemes, such as Dijstra's algorithm and incremental OSPF. Results show that CSPTR can greatly eliminate unnecessary SPT recomputation and reduce large amounts of the flooding overheads.