4711

4430

كارشناسي ارشد

معماري كامپيوتر

اصفهان: دانشگاه صنعتي اصفهان، دانشكده برق و كامپيوتر

1388

ده،89،[I]ص.: مصور،جدول،نمودار

ص.ع.به فارسي و انگليسي

رسول موسوي

مسعود رضا هاشمي

3/8/88

جواد عسگري، پژمان خديوي

مهندسي برق و كامپيوتر

ID4430

به فارسي و انگليسي: قابل رويت در نسخه ديجيتالي

An Optimal Method to Improve Wireless Sensor Networks Lifetime and Reliability via Boolean Satisfiability Maryam Ashouri m ashouri@ec iut ac ir Date of Submission April 15 2009 Department of Electical and Computer Engineering Isfahan University of Technology Isfahan 84156 83111 Iran Degree M Sc Language Farsi Supervisors Dr Seyed Rasoul Mousavi srm@cc iut ac ir Dr Shadrokh Samavi samavi96@cc iut ac irAbstractOne of the important concerns in wireless sensor networks is network lifetime which isdefined as the time span that all targets can be thoroughly covered Random and densedeployment of sensors in many applications may impose some coverage redundancy in thenetwork Under these conditions judicious power management and sensor scheduling canconsiderably extend network lifetime One way to reduce energy consumption is to dividesensors into disjoint groups called covers each of which can cover all targets and toactivate them iteratively in a round robin fashion At each time interval only the sensorsfrom the current active set are responsible for monitoring the targets while all other nodesare in sleep or power saving mode The more covers can be found the longer sensornetwork can be prolonged Obtaining the maximum number of such covers is known asDSC problem which is proved to be NP hard Existing heuristic algorithms either getunsatisfactory solutions in some cases or take unacceptable computation time whichmakes them inapplicable in medium large dimensions The aim of this research is findingan effective method to improve lifetime and reliability of wireless sensor networks Wefirst propose an optimal method to solve this optimization problem that is to split the set ofsensors into maximum number of covers The proposed method is based on thetransformation of the problem into the well known Boolean satisfiability SAT problem Simulation results show that this method can lead to a large reduction in computation timemeanwhile produces optimal solutions We then investigate the sensor scheduling for K coverage problem in which targets are required to be monitored by at least K sensorsthroughout the whole network lifetime Based on the proposed method we extend thisapproach to a reliable coverage problem and evaluate its performance through severalsimulations The algorithm is simple fast and according to the simulations significantlyincreases the longevity of sensor network in scenarios which require stronger monitoringand fault tolerant capability Key words Boolean Satisfiability Disjoint Set Cover Life Time NP hard Wireless SensorNetworks

رسول موسوي

مسعود رضا هاشمي

جواد عسگري، پژمان خديوي