Exploiting neighborhood information in wireless networks: Channel assignment and replica detection.

摘要

Distributed networking paradigms, e.g., mesh/ad hoc/sensor networking, are envisioned as a fundamental building block of the "any time, any where" next generation wireless networks. In these paradigms, it is often the case that neighboring nodes need to cooperate together to perform a task, e.g., resource allocation, misbehavior detection, routing, sensing, etc. The first step in performing any of these applications is for these nodes to exploit their neighborhood information in order to facilitate cooperation. In other words, nodes need to know "how to make use of their neighborhood information to facilitate their task execution?". This neighborhood exploitation issue directly determines the performance, efficiency, and security of the network.;In this research, we study the exploitation of neighborhood information and focus on two major problems: channel assignment in multi-channel wireless mesh networks, and replica detection in static wireless sensor networks (WSNs) and mobile ad hoc networks (MANETs). In multi-channel wireless mesh networks, as decentralized channel assignment decisions are made over nodes spread over the network, such decisions have to be granted with low interference, low delay and high throughput while keeping the network connected and the channel assignments fair. In our approach, we first pre-assign each node with a unique channel codeword based on s-disjunct codes. By exploiting neighbors' channel codewords and their s-disjunct property, we then develop two localized channel assignment algorithms, one for unicast and one for local broadcast (as defined in [1]). We also identify the conditions that interference-free communication can be achieved for both unicast and local broadcast, and the scenarios when the channel assignment algorithm for unicast can reach 100% throughput. The probability analysis on the above conditions, as well as channel diversity and transmission delay are researched as well.;In static sensor networks and mobile ad hoc networks, we focus on the node replication detection problem. Specifically, we proposed two replica detection schemes, one hybrid detection scheme for sensor networks detects replicas either locally or at the base station based on social fingerprint, and one localized approach for MANETs detects node replication attacks from space domain. In the former scheme, each node computes a social fingerprint characterizing the local neighborhood (neighbors). Since each node's neighborhood is unique in the network, the replica can be detected by discovering fingerprint mismatch. In the latter scheme, each node maintains a cryptographic one-way hash chain. When two nodes meet, they first exchange their time-stamped location claims associated with their one-way hash values, then check the information they kept for other nodes. Once they find paradox information, the replica attack can be detected. Our analysis indicates that both schemes provide a high detection accuracy disregarding node collusion and the number/distribution of replicas/compromised nodes. Moreover, these schemes are naturally extensible to other classes of static/mobile networks in which nodes can be physically captured and replicated by adversaries.;The major contributions of this dissertation are multi-fold. Firstly, the channel assignment approach for local broadcast is the first to stand for effectively supporting local broadcast in multi-channel networks. Secondly, the channel assignment approach for unicast can reach 100% throughput under the primary interference model and achieve interference free communication under certain conditions. Thirdly, the social fingerprint based replica detection scheme is the first to provide realtime detection of node replication attacks in an effective and efficient way in static sensor networks. And lastly, to our best knowledge, the replica detection scheme for MANETs is the only approach that supports mobile networks while placing no restrictions on the number and distribution of the cloned frauds and on whether the replicas collude or not.