TY - JOUR

T1 - Maximum scan statistics and channel assignment problems in homogeneous wireless networks

AU - Ik, Tsi-Ui

PY - 2009/5/17

Y1 - 2009/5/17

N2 - In wireless networks, to avoid collisions of simultaneous transmissions over the same channel, adjacent nodes are assigned distinct channels, and the least number of channels used in an assignment is called the chromatic number. The determination of the chromatic number is NP-hard. In this paper, we introduce an analytic tool called maximum scan statistics. For a finite point set V and a convex compact set C, the maximum scan statistic of V with respect to the scanning set C is the largest number of points in V covered by a copy C. Based on the study of asymptotic maximum scan statistics, we obtain the asymptotics of the maximum degree and the clique number of homogeneous wireless networks. The results imply that the chromatic number is almost surely at most four times the clique number. We further prove that the approximation ratios of some vertex-ordering-based First-Fit channel assignment algorithms are almost surely bounded by 2. In the analysis, we also learn that the chromatic number is almost surely at most twice the clique number.

AB - In wireless networks, to avoid collisions of simultaneous transmissions over the same channel, adjacent nodes are assigned distinct channels, and the least number of channels used in an assignment is called the chromatic number. The determination of the chromatic number is NP-hard. In this paper, we introduce an analytic tool called maximum scan statistics. For a finite point set V and a convex compact set C, the maximum scan statistic of V with respect to the scanning set C is the largest number of points in V covered by a copy C. Based on the study of asymptotic maximum scan statistics, we obtain the asymptotics of the maximum degree and the clique number of homogeneous wireless networks. The results imply that the chromatic number is almost surely at most four times the clique number. We further prove that the approximation ratios of some vertex-ordering-based First-Fit channel assignment algorithms are almost surely bounded by 2. In the analysis, we also learn that the chromatic number is almost surely at most twice the clique number.

KW - Channel assignment

KW - Chromatic numbers

KW - Clique numbers

KW - Inductivities

KW - Maximum scan statistics

KW - Wireless ad hoc networks

UR - http://www.scopus.com/inward/record.url?scp=64249116672&partnerID=8YFLogxK

U2 - 10.1016/j.tcs.2009.02.027

DO - 10.1016/j.tcs.2009.02.027

M3 - Article

AN - SCOPUS:64249116672

VL - 410

SP - 2223

EP - 2233

JO - Theoretical Computer Science

JF - Theoretical Computer Science

SN - 0304-3975

IS - 21-23

ER -