Practical cross-layer routing and channel assignment in cognitive radio ad hoc networks

摘要

In the heterogeneous and unreliable channel environment of cognitive radio ad hoc networks (CRAHNs), a multipath route with channel assigned is preferable in both throughput and reliability. The cross-layer multipath routing and channel assignment in CRAHNs is becoming a challenging issue. In this paper, this problem is characterized, formulated, and showntobe in the form of mixed integer programming. For this Non-deterministic Polynomial-time (NP)-hard problem, the deficiency of the widely used linearization and sequential fixing algorithm is first analyzed. The main contribution of this paper is the development of a new backtracking algorithm with feasibility checking to search optimal solutions and a heuristic algorithm with high feasible solution-obtained probability (HHFOP) for distributed application in CRAHNs. Through feasibility checking and solution bounds validating, backtracking algorithm with feasibility checking cuts off unnecessary searching space in early stage without loss of optimal solutions, making it much more efficient than brute searching. For practical application in CRAHNs with polynomial complexity, HHFOP first computes the maximal-supported throughput through link-channel assignment and link-capacity coordination for each candidate path. Then the paths are combined, and the route throughput is optimized. Extensive simulation results demonstrate that HHFOP can achieve a high feasible solution-obtained probability with little throughput degradation compared with linearization and sequential fixing algorithm, indicating its practicability for distributed applications in CRAHNs. Copyright (c) 2013 John Wiley & Sons, Ltd.