A Number Of Resource Sharing Problem In Wireless Sensor Networks

The Wireless Sensor Network (WSN) is a kind of Ad hoc network that consists of one or few sinks and many sensor nodes. The sensor nodes and sinks are usually equipped with a processing unit and a wireless communication unit in order to transfer data. As lots of efforts have been made in recent years on both theoretical and applicative aspects of WSNs, large scale deployment of WSNs has been made possible. Among many proposed network architectures, a kind of large scale multi-sink WSN has provided a promising way to many applications. Multiple sinks in the network act as data collectors working together to collect data from the sensors. They can also perform as end users of WSN when they do not contact each other directly. In either case, fairness among the sinks is important. This dissertation will focus on such a topic. We first define several related fairness issues, then analyze them based on various theoretical models and finally we propose algorithms to solve these problems.Four perspectives are of special interests of this dissertation.(i) Max-min fair capacity sharing problem is defined and discussed in dense WSNs. The analysis will be based on a disc shaped query model and a stream based traffic model. Under these assumptions, the query region of a sink is limited by the bandwidth of both sensors and sinks. Thus, sinks have to cooperate with the sensors in order to achieve the desired results. Explicit expression of max-min fair query radius under two-sink case is derived and the problem under multi-sink case is solved with a distributed heuristic approach. Extensive simulations show the effectiveness of the proposed algorithms and reveal some interesting new problems as well.(ii) The network with a max-min fair query configuration has been shown to be poorly utilized by the previous simulation. Besides, it is well known that there is generally a trade-off between fairness and efficiency. The second part of this dissertation deals with the capacity problem in multi-sink WSNs. The network coverage will be considered as an important factor for network capacity and the Max-min fair queries are proved, by analyzing a two-sink case, unable to achieve the highest network coverage under certain situation, Similar phenomenon has been found in multi-sink WSNs in an intensive simulation study.(iii) Fairness among the sinks will also be studied with a hop based query model. Under this case, the discrete value of the query radius no longer promises the existence of the max-min fair solution, thus lexicographical max-min fairness will be exploited instead. We also found it is convenient to model the lexicographical max-min fairness problem among multiple sinks with the Multi-dimensional Multiple choice Knapsack Problem (MMKP). Furthermore, the traditional optimization objective, which maximizes the sum of the utility of all items in the knapsack, could also be used to maximize the overall utility of sinks in our case. Based on these observations, we propose a unified framework for the problem description. This framework, firstly, is able to formulate different optimization problems originated in multi-sink WSNs; and secondly, implies simple implementation of uniformed algorithms solving the problems. Extensive simulations are carried out to evaluate the performance of the algorithms.(iv) Mobility of sinks has to be supported when the above mechanisms work in a practical scenario. We assume geographical position based routing protocol is in use and investigate the basic problem that how mobile sinks should notify the sensors with their up-to-date position. Three simple update strategies, Neighbor Update, Unicast Update and Flooding Update, are investigated. Control overhead, sensor energy consumption, end-to-end packet delay and average path length are considered as the performance metrics. Explicit expressions for the average energy consumption are derived for each strategy. Based on the analytical results, an adaptive position update mechanism is proposed to select the least cost strategy to perform the update based on the observed network condition. Various network configurations are simulated and the simulation data are well conformed to the analytical results. Compared with a routing protocol specially designed for WSN with mobile sinks, namely TTDD, the simple geographical position based routing combined with the proposed position update mechanism achieves highest performance in almost all simulated scenarios.This dissertation concentrates on WSN. However, the problems and solutions discussed here may also be valid in other large scale networks such as wireless mesh networks and overlay networks.