Topology design for multihop cellular network

Public communication systems often crash in large scale disasters, critically hindering coordination among disaster responders. Survival rates can be greatly increased by breaking communication bottlenecks. We proposed a contingency cellular network (CCN) that aims to provide communication service to large amount of voluntary workers and victims in the early hours. CCN connects crashed base stations using wireless links to construct a multihop cellular network. Since, topology design problem is one of the important issues of CCN design. This research proposes two algorithms to solve the network topology design problem of CCN which is constructed by multiple operators' base stations. The degree of emergency and population of each stricken area are taken as the priority measure as well as the available resources as the constraint to determine the network topology. The network topology design problem is formulated as a K-Maximum Spanning Tree Problem with degree bound and had been proven NP Hard. A binary integer linear programming (BILP) algorithm is proposed to solve the optimal solution. Since the network topology is needed in urgent, a heuristic algorithm is also proposed to solve this problem quickly.