How many wireless resources are needed to resolve the hidden terminal problem?

A novel wireless resource partition method is proposed to theoretically solve the hidden terminal problem (HTP) for wireless networks with uniform transmission ranges, and known, stationary node locations. A hidden terminal graph (HTG) representation is used to capture the potential hidden terminal interference among wireless nodes. The wireless resource partitioning solution of the HTP problem is cast as a graph-coloring problem on the HTG. Under a unit-disk wireless transmission range model, a novel, efficient, constructive solution to the HTG graph-coloring problem is proposed. Specifically, by spatially grouping wireless nodes into a hexagonal grid coordinate system, it is shown that the supremum of chromatic number of a HTG can be bounded by [6,12], regardless of the number of nodes or how the nodes are distributed spatially. Moreover, 12 is also the maximum number of wireless resource partitions needed to resolve the corresponding HTP problem. Extensive simulation results reveal that the performance of this hex-coloring method is comparable to existing heuristic graph-coloring methods such as DSATUR for problems with moderate size (a few hundreds of nodes). When the problem size scales up to a few thousands of nodes, the hex-coloring solution consistently achieves superior solutions (fewer wireless resources required) while consuming 3 orders of magnitude less computing time.