Graduate Exam Abstract

Herath M N Dilum Bandara

M.S. Final

July 21, 2008, 2.00pm

Engineering B101

Top-Down Clustering Based Self-Organization of Collaborative Wireless Sensor Networks

Abstract: Recent advances in Wireless Sensor Network (WSN) technology are enabling the deployment of large-scale and collaborative sensor networks. Energy efficient operation, channel contention, latency, management, and security of such networks are complex and critical issues that have to be addressed with large WSN deployments. Collaborative sensor networks further require dynamic grouping of nodes observing similar events and communication within such groups and across different groups. Cluster based organization of large sensor networks is the key for many techniques that addresses these issues. A backbone network in the form of a cluster tree can further enhance upper layer functions such as routing, broadcasting, and in-network query processing. <br>A configurable cluster and cluster tree formation algorithm is presented that is independent of network topology and does not require a-priori neighborhood information, location awareness, or time synchronization. Configurable parameters of the algorithm can be used to form cluster trees with desirable properties such as controlled breadth and depth, uniform cluster size, and more circular clusters. Message complexity of the algorithm grows linearly with the number of nodes in the network, hence algorithm scales well into large networks. Simulation based analysis show that the algorithm forms more circular and uniform clusters, cluster tree with lower depth, and more importantly forms a more ordered structure in the network. Closeness of clusters to hexagonal packing is evaluated. The structure imposed by the algorithm makes it applicable to broad classes of applications. <br>The proposed cluster tree based routing strategy facilitates both node-to-sink and node-to-node communication. Hierarchical addresses that reflect the parent-child relationship of cluster heads is used to route data along the cluster tree. Utilization of cross-links among neighboring cluster heads and a circular link within the network seems to doubles the capacity of the network. Under ideal conditions, this approach guarantee delivery of events/queries and has a lower overhead compared to routing strategies such as rumor routing and ant routing. The cluster tree formed by our algorithm is used to identify and form Virtual Sensor networks (VSNs), an emerging concept that supports resource efficient collaborative WSNs. Our implementation of VSN is able to deliver unicast, multicast, and broadcast traffic among nodes observing similar events efficiently. The algorithm is further extended to support the formation of a secure backbone that can facilitate secure upper layer functions and dynamic distribution of cryptographic keys in collaborative sensor networks.

Adviser: Prof. Anura P. Jayasumana
Co-Adviser: .
Non-ECE Member: Dr. Daniel F. Massey
Member 3: Prof. V. Chandrasekhar
Addional Members: .


Program of Study: