Abstract:

Given a set S = {S1 , . . . ,Sn} of n homogeneous wireless sensors deployed in a two dimensional area , a source point s and a destination point t , the least protected point p along a path (s ,t ) is that point such that the Euclidean distance between p and its closest sensor node Si is maximum . This distance between p and S _{i} is called the Cover value of the path P (s ,t ) . The Best Coverage Path between s and t , denoted as BCP (s ,t ) , is the path that has the minimum cover value . Although there exists efficient algorithms to compute BCP in O (n log n ) time , the presence of obstacles inside the two dimensional area has not been addressed in the literature . In this thesis , we consider the problem of computing BCP (s ,t ) in the presence of m line segment obstacles distributed among n sensors . Because of the presence of obstacles , sensing by sensors can get obstructed and the constructed path may have to detour which pose significant challenges . We propose three algorithms to compute two different variations of the BCP (s ; t ) problem in the presence of obstacles . In particular , for the case of opaque obstacles , i .e . , which obstruct both the sensing as well the computed path , we develop an algorithm that computes BCP (s ,t ) in $O ( (m^{2}n^{2} + n^{4} ) \log (mn+n^{2} ) ) ) time . The underlying idea is to leverage the concept of a quartic time Constrained and Weighted Voronoi diagram among obstacles and creating its dual . For the case of transparent obstacles that cannot obstruct sensing but the computed path has to avoid obstacles , we develop two algorithms that compute BCP (s ,t ) . The first algorithm runs in O (nm^{2}+n^{3} ) time using the visibility graph data structure , while the second one is an approximation algorithm and requires O (nm+n^{2} )time using spanners of the visibility graph . The approximation factor of the cover value is O nk where k is the stretch factor of the spanner graph . The proofs of correctness of the three proposed algorithms are also presented in this thesis . 