Coordinate repair and medial axis detection in virtual coordinate based sensor networks - Mahindre, Gunjan S., author; Jayasumana, Anura, advisor; Luo, J. Rockey, committee member; Malaiya, Yashwant, committee member (Colorado State University. Libraries, 2014)
Wireless Sensor Networks (WSNs) perform several operations like routing, topology extraction, data storage and data processing that depend on the efficiency of the localization scheme deployed in the network. Thus, WSNs need to be equipped with a good localization scheme as the addressing scheme affects the performance of the system as a whole. There are geographical as well as Virtual Coordinate Systems (VCS) for WSN localization. Although Virtual Coordinate (VC) based algorithms work well after system establishment, they are hampered by events such as node failure and link failure which are unpredictable and inevitable in WSNs where sensor nodes can have only a limited amount of energy to be used. This degrades the performance of algorithms and reduces the overall life of the network. WSNs, today, need a method to recover from such node failures at its foundation level and maintain its performance of various functions despite node failure events. The main focus of this thesis is preserving performance of virtual coordinate based algorithms in the presence of node failure. WSNs are subject to changes even during their operation. This implies that topology of the sensor networks can change dynamically throughout its life time. Knowing the shape, size and variations in the network topology helps to repair the algorithm better. Being centrally located in the network, medial nodes of a network provides us with information such as width of the network at a particular cross-section and distance of network nodes from boundary nodes. This information can be used as a foundation for applications such as network segmentation, VC system implementation, routing scheme implementation, topology extraction and efficient data storage and recovery. We propose a new approach for medial axis extraction in sensor networks. This distributed algorithm is very flexible with respect to the network shape and size. The main advantage of the algorithm is that, unlike existing algorithms, it works for networks with low node degrees. An algorithm for repairing VCS when network nodes fail is presented that eliminates the need for VC regeneration. This helps maintain efficient performance for all network sizes. The system performance degrades at higher node failure percentages with respect to the network size but the degradation is not abrupt and the system maintains a graceful degradation despite sudden node failure patterns. A hierarchical virtual coordinate system is proposed and evaluated for its response to network events like routing and node failures. We were also able to extract medial axis for various networks with the presented medial axis detection scheme. The networks used for testing fall under a range of shapes and an average node degree from 3 to 8. Discussions over the VC repair algorithm and the novel medial axis extraction scheme provide an insight into the nature of proposed schemes. We evaluate the scope and limitations for VCS repair algorithm and medial axis detection scheme. Performance of the VC repair algorithm in a WSN is evaluated over various conditions simulated to represent a practical node failure events to gauge the system response through routing percentage and average hop count over the network. We compare the results obtained through our medial axis detection scheme with existing state-of-the-art algorithm. The results show that this scheme overcomes the shortcomings of the medial axis detection schemes. The proposed medial axis detection technique enables us to extract the information held by a medial axis of a sensor network. The VC repair algorithm and the new medial axis extraction scheme perform very efficiently to make a WSN tolerant of node failure events.