Skip to main content
SUPERVISOR
MasoudReza Hashemi,Seyed Rasul Moosavi,Shadrokh Samavi
مسعودرضا هاشمی (استاد مشاور) سید رسول موسوی (استاد راهنما) شادرخ سماوی (استاد راهنما)
 
STUDENT
Maryam Ashouri
مریم آشوری

FACULTY - DEPARTMENT

دانشکده مهندسی برق و کامپیوتر
DEGREE
Master of Science (MSc)
YEAR
1385

TITLE

An Optimal Method to Improve Wireless Sensor Networks Lifetime and Reliability via Boolean Satisfiability
One of the important concerns in wireless sensor networks is network lifetime, which is defined as the time span that all targets can be thoroughly covered. Random and dense deployment of sensors in many applications may impose some coverage redundancy in the network. Under these conditions, judicious power management and sensor scheduling can considerably extend network lifetime. One way to reduce energy consumption is to divide sensors into disjoint groups, called covers, each of which can cover all targets and to activate them iteratively in a round robin fashion. At each time interval, only the sensors from the current active set are responsible for monitoring the targets, while all other nodes are in sleep or power-saving mode. The more covers can be found, the longer sensor network can be prolonged. Obtaining the maximum number of such covers is known as DSC problem which is proved to be NP-hard. Existing heuristic algorithms either get unsatisfactory solutions in some cases or take unacceptable computation time, which makes them inapplicable in medium (large) dimensions. The aim of this research is finding an effective method to improve lifetime and reliability of wireless sensor networks. We first propose an optimal method to solve this optimization problem; that is to split the set of sensors into maximum number of covers. The proposed method is based on the transformation 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 time meanwhile 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 sensors throughout the whole network lifetime. Based on the proposed method, we extend this approach to a reliable coverage problem and evaluate its performance through several simulations. The algorithm is simple, fast, and according to the simulations, significantly increases the longevity of sensor network in scenarios which require stronger monitoring and fault-tolerant capability. Key words: Boolean Satisfiability, Disjoint Set Cover, Life Time, NP-hard, Wireless Sensor Networks.
یکی از ملاحظات مهم در شبکه‌های حسگر بی‌سیم، طول عمر شبکه می‌باشد که به‌صورت بازه‌ی زمانی تعریف می‌شود که تمام هدف‌ها به‌طور کامل پوشش داده می‌شوند. توزیع متراکم و تصادفی حسگرها در بسیاری از کاربردها، ممکن است مقداری افزونگی پوشش در شبکه اعمال نماید. تحت این شرایط، مدیریت مناسب توان و زمان‌بندی حسگر می‌تواند طول عمر شبکه را به‌طور قابل ملاحظه‌ای افزایش دهد. راهی برای کاهش مصرف توان تقسیم حسگرها به گروه‌های مجزا، به‌نام پوشش، که‌ هریک به‌تنهایی می‌تواند تمام هدف‌ها را پوشش دهد، و فعال کردن آنها به‌صورت نوبتی باشد. در هر بازه‌ی زمانی، تنها حسگرهای پوشش فعال، مسئول مانیتور کردن هدف‌ها هستند در حالی‌که تمام گره‌های دیگر در حالت خواب یا ذخیره‌ی انرژی می‌باشند. هرچه پوشش‌های بیشتری پیدا شود، طول‌عمر شبکه بیشتر افزایش خواهد یافت. به‌دست آوردن ماکزیمم تعداد این پوشش‌ها به‌نام مسئله‌ی DSC شناخته شده که ثابت می‌شود NP-سخت است. الگوریتم‌های مکاشفه‌ای موجود برای این مسئله در مواردی دارای راه‌حل‌های نامطلوب و زمان محاسبه غیرقابل قبول می‌باشند که آنها را در ابعاد متوسط و بزرگ غیرعملی می‌سازد. هدف این تحقیق، ارائه‌ی راه‌‌کاری مؤثر برای بهبود طول‌عمر و قابلیت اطمینان شبکه‌های حسگر بی‌سیم می‌باشد. ما ابتدا روشی بهینه برای حل این مسئله‌ی بهینه‌سازی، یعنی تقسیم مجموعه‌ی حسگر‌ها به ماکزیمم تعداد پوشش ارائه می‌کنیم. الگوریتم پیشنهادی، مبتنی بر تبدیل مسئله به یک مسئله‌ی ارضاپذیری معروف، به نام SAT می‌باشد. نتایج شبیه‌سازی نشان می‌دهد که روش پیشنهادی می‌تواند منجر به تولید راه‌حل‌های بهینه و در عین حال کاهش چشمگیر در زمان محاسبه گردد. در ادامه ما مسئله‌ی زمان‌بندی حسگر برای مسئله K-پوشش را مورد بررسی قرار می‌دهیم، که در آن لازم است هدف‌ها در تمام طول‌عمر شبکه حداقل توسط K حسگر پوشش داده شوند. بر اساس روش پیشنهادی، این ایده برای یک مسئله‌ی پوشش مطمئن تعمیم داده شده است و کارایی آن با شبیه‌سازی‌های متعدد مورد ارزیابی قرار گرفته است. این روش ساده و سریع می‌باشد و با توجه به شبیه‌سازی‌ها، طول عمر شبکه‌ی حسگر را در سناریو‌هایی که نیازمند مانیتورینگ دقیق‌تر و تحمل‌پذیری خطا هستند، به‌طور قابل ملاحظه‌ای افزایش می‌دهد. واژه‌های کلیدی: ارضاپذیری، مجموعه‌ی پوشش مجزا، طول‌ عمر، NP-سخت ، شبکه‌های حسگر بی‌سیم

ارتقاء امنیت وب با وف بومی