Title page for ETD etd-07262010-122611

Document Type Master's Dissertation
Author Nicholls, Gareth Michael
URN etd-07262010-122611
Document Title Location inaccuracies in WSAN placement algorithms
Degree MSc
Department Computer Science
Advisor Name Title
Prof D G Kourie Committee Chair
Prof T Strauss Committee Co-Chair
  • Geo-information systems
  • voronoi polygons
  • delaunay triangle
  • node
  • mote
  • coverage hole
Date 2010-09-02
Availability unrestricted

The random deployment of Wireless Sensor and Actuator Network (WSAN) nodes in areas often inaccessible, results in so-called coverage holes i.e. areas in the network that are not adequately covered by nodes to suit the requirements of the network. Various coverage protocol algorithms have been designed to reduce or eliminate coverage holes within WSANs by indicating how to move the nodes. The effectiveness of such coverage protocols could be jeopardised by inaccuracy in the initial node location data that is broadcast by the respective nodes. This study examines the effects of location inaccuracies on five sensor deployment and reconfiguration algorithms They include two algorithms which assume that mobile nodes are deployed (referred to as the VEC and VOR algorithms); two that assume static nodes are deployed (referred to as the CNPSS and OGDC algorithms); and a single algorithm (based on a bidding protocol) that assumes a hybrid scenario in which both static and mobile nodes are deployed. Two variations of this latter algorithm are studied.

A location simulation tool was built using the GE Smallworld GIS application and the Magik programming language. The simulation results are based on three above-mentioned deployment scenarios; mobile, hybrid and static.

The simulation results suggest the VOR algorithm is reasonably robust if the location inaccuracies are somewhat lower than the sensing distance and also if a high degree of inaccuracy is limited to a relatively small percentage of the nodes. The VEC algorithm is considerably less robust, but prevents nodes from drifting beyond the boundaries in the case of large inaccuracies. The bidding protocol used by the hybrid algorithm appears to be robust only when the static nodes are accurate and there is a low degree of inaccuracy within the mobile nodes. Finally the static algorithms are shown to be the most robust; the CPNSS algorithm appears to be immune to location inaccuracies whilst the OGDC algorithm was shown to reduce the number of active nodes in the network to a better extent than that of the CPNSS algorithm.

Copyright 2010, University of Pretoria. All rights reserved. The copyright in this work vests in the University of Pretoria. No part of this work may be reproduced or transmitted in any form or by any means, without the prior written permission of the University of Pretoria.

Please cite as follows:

Nicholls, GM 2010, Location inaccuracies in WSAN placement algorithms, MSc dissertation, University of Pretoria, Pretoria, viewed yymmdd < http://upetd.up.ac.za/thesis/available/etd-07262010-122611/ >


  Filename       Size       Approximate Download Time (Hours:Minutes:Seconds) 
 28.8 Modem   56K Modem   ISDN (64 Kb)   ISDN (128 Kb)   Higher-speed Access 
  dissertation.pdf 2.08 Mb 00:09:37 00:04:56 00:04:19 00:02:09 00:00:11

Browse All Available ETDs by ( Author | Department )

If you have more questions or technical problems, please Contact UPeTD.