Analyzing Resilience to Node Misbehaviors in Wireless Multi-Hop Networks

The network resilience has been studied as a fault tolerance measure in wired networks for decades; however, little effort has been made to analyze the resilience of wireless multi-hop networks, especially in the presence of misbehaving nodes. In this work, we study such a problem: whether there exists an overlay achieving "strong" resilience when misbehaving nodes are present in the underlying wireless multi-hop network. To address this problem, we first introduce two new metrics, k-connected survivability and resilience capacity. The former metric is used to measure the network connectivity probabilistically; while the latter one is used to evaluate the ability of accommodating misbehaving nodes deterministically. We then derive an approximate representation of the k-connected survivability, and provide the close-form representations of resilience capacity for k = 1 and k = 2 and a heuristic algorithm to calculate it when k ges 3. Finally, based on our analytical results, we prove that an overlay can achieve the derived resilience by satisfying three conditions: (i) containing all and only cooperative nodes of the original network; (ii) keeping the minimum cooperative degree at least k; (iii) having Theta (log₂ N) neighbors of each node in average.