MS, University of Cincinnati, 2012, Engineering and Applied Science: Computer Science

Reliability and fault tolerance are an important part of data gathering at a base station (sink) in a wireless sensor network. Due to the uncertain environments of the network it becomes necessary to have robustness and information security integrated into the routing schemes. Multipath routing using independent trees is an eective way to achieve it. In real world applications, every node of the network does not have homogeneous connectivity to the base station. A more practical approach and a recent research area is having heterogeneous node connectivity with independent trees which are not necessarily spanning. A recent algorithm, referred to as DAG Independent Trees that gives vertex independent trees in heterogeneously connected directed acyclic graphs (DAGs) is discussed. The problem of realizing the vertex connectivity in independent trees is NP-complete. Therefore, an experimental analysis of the connectivity realized with independent trees given by the algorithm, and vertex connectivity from the nodes to sink is given. The results show that the algorithm nearly satises the condition that all nodes realize at least half the connectivity. A close approximation to the connectivity at more than half the nodes is achieved. In the case, when the algorithm does less than half the connectivity for most of the nodes, an optimization of the algorithm is given. The optimization over all permutations of the sink nodes is presented in the case when it does not fair well.

Committee: Kenneth Berman PhD (Committee Chair); Fred Annexstein PhD (Committee Member); Anca Ralescu PhD (Committee Member) Subjects: Computer Science