______________________________________________________________________ Date: Friday 9 March 2012 Time: 11:15 Venue: Room 1213, House 1, ITC, Polacksbacken, Uppsala University ______________________________________________________________________ Optimised Fault-tolerant Relay Deployment for Wireless Sensor Networks Ken Brown (http://www.cs.ucc.ie/~kb11/) Cork Constraint Computation Centre University College Cork Ireland Wireless Sensor Networks can be unreliable, because of failures of individual nodes or links. To be robust, the topology should provide alternative paths from nodes to the sinks, so that when failures occur the routing protocol can still offer reliable delivery. Once the positions of the sensor nodes have been established, we can add additional wireless relay nodes which simply forward data. Designing the topology of the network is then a trade-off between robustness and the cost of the additional relay nodes. We use a GRASP (Greedy randomised adaptive search procedure) to search for solutions, and consider two different approaches. The first ensures that each sensor node has k node-disjoint paths, and minimises the number of relay nodes to achieve it. The second introduces a new centrality measure, based on the number of other nodes that would lose connectivity or acceptable alternative paths if the current node fails, and then deploys relay nodes to minimise the maximum centrality in the network. We demonstrate empirically that the first approach is more efficient that standard algorithms for achieving k-connectivity, and that the second approach requires fewer relay nodes and has a faster runtime. Finally, we evaluate the deployments in simulation, demonstrating that the centrality-based deployments offer comparable robustness to the other algorithms. ______________________________________________________________________ Directions: http://www.polacksbacken.uu.se/Find_us/