New measures for characterizing the significance of nodes in wireless ad hoc networks via localized path-based neighborhood analysis

The synergy between social network analysis and wireless ad hoc network protocol design has recently created increased interest for developing methods and measures that capture the topological characteristics of a wireless network. Such techniques are used for the design of routing and multicasting protocols, for cooperative caching purposes and so on. These techniques are mandatory to characterize the network topology using only limited, local connectivity information—one or two hop information. Even though it seems that such techniques can straightforwardly be derived from the respective network-wide techniques, their design presents significant challenges since they must capture rich information using limited knowledge. This article examines the issue of finding the most central nodes in neighborhoods of a given network with directed or undirected links taking into account only localized connectivity information. An algorithm that calculates the ranking, taking into account the N-hop neighborhood of each node is proposed. The method is compared to popular existing schemes for ranking, using Spearman’s rank correlation coefficient. An extended, faster algorithm which reduces the size of the examined network is also described.