For high-density networks, several studies have proposed field-based routing paradigms to uniformly distribute the traffic load throughout the network. However, as network density decreases, we observe major shortcomings of the current state-of-the-art: (i) fewer number of neighbors reduce the number of available paths and leads to path merging and (ii) the paths directed towards the border of the network merge into a single path. These path merging effects decrease significantly the energy balance, and as consequence, the lifetime of the network. In this paper, we propose a novel mechanism to enable a better load balancing for single-source and multiple-source scenarios. Our evaluations demonstrate that by using the proposed methodology, the network lifetime can be prolonged between 30% and 40%. ... Read more

The simplicity and low-overhead of random walks have made them a popular querying mechanism for Wireless Sensor Networks. However, most of the related work is of theoretical nature and present two important limitations. First, they are mainly based on simple random walks, where at each step, the next hop is selected uniformly at random among neighbors. This mechanism permits analytical tractability but wastes energy by unnecessarily visiting neighbors that have been visited before. Second, the studies usually assume static graphs which do not consider the impact of link dynamics on the temporal variation of neighborhoods. In this work we evaluate the querying performance of Non-Revisiting Random Walks (NRWs). At each step, NRWs avoid re-visiting neighbors by selecting the next hop randomly among the neighbors with the minimum number of visits. We evaluated Pull-only and Pull-Push queries with NRWs in two ways: (i) on a test-bed with 102 tmotes and (ii) on a simulation environment considering link unreliability and asymmetry. Our main results show that non-revisiting random walks significantly improve upon simple random walks in terms of querying cost and load balancing, and that the push-pull mechanism is more efficient than the push-only for query resolution. ... Read more

In wireless sensor network applications where each node sends a packet to a sink, the stochastic nature of the link affects the delivery rate (total number of packets delivered at the sink). Based on a simple analytical model, we study the statistical properties of the delivery rate for scenarios without link or transport layer retransmission (best-effort routing). For these best-effort scenarios, we derive bounds for the expectation and variance of the delivery rate for single-sink and multiple-sink architectures. Our analytical findings are further validated through simulations using a realistic link-layer model. ... Read more

This work presents a distributed routing protocol to help mobile users locate items in passive wireless environments. In these environments, a mobile user can detect items that are in its proximity, but items can not communicate directly with each other. For example, an area where passive RFID tags are embedded in the environment and mobile users are provided with RFID readers. The localization protocol is based on the following idea: while searching for a specific node, mobile users populate the memory of the nodes they encounter with information about the nodes they have already seen; later, this information is used to guide other users. The contribution of our work is to demonstrate the feasibility of the proposed protocol, in particular, we provide: (a) a lower bound for the required memory space (in the nodes) to store routing information, (b) a proof that disseminate-whilesearch routing is loop-free and (c) an study on the extent of user mobility required to disseminate the routing information. A proof-of-concept of the proposed protocol was implemented in a small test-bed of MicaZ motes resembling a passive environment. ... Read more