Award Date


Degree Type


Degree Name

Master of Science (MS)


Computer Science

First Committee Member

Laxmi P. Gewali

Number of Pages



Construction of interference reduced routes is an all-important problem in sensor network. We propose a model for extracting a small size backbone network from a given background network. The extracted network possesses the property of reduced static interference. A backbone structure, constructed on the top of a planar sensor network can be used to route message with lower interference. We propose two centralized algorithms for constructing the backbone network. The first algorithm is based on the spanning tree construction of inner holes of sensor network. The second algorithm builds the backbone network by using the Delaunay triangulation of the center of gravity of holes in the network, which runs in O(n2) time. We also present a distributed localized implementation of the proposed algorithm by using the quasi Voronoi diagram and medial axis formed by the distribution of network holes. We describe an experimental investigation of the proposed algorithm. The results of the simulation show that the routing guided by the proposed backbone network is effective in reducing interference.


Interference; Networks; Reduced; Routing; Sensor

Controlled Subject

Computer science

File Format


File Size

1576.96 KB

Degree Grantor

University of Nevada, Las Vegas




If you are the rightful copyright holder of this dissertation or thesis and wish to have the full text removed from Digital Scholarship@UNLV, please submit a request to and include clear identification of the work, preferably with URL.


IN COPYRIGHT. For more information about this rights statement, please visit