عنوان پایان‌نامه
کیفیت اطلاعات در شبکه های حسگر بی سیم
- رشته تحصیلی
- مهندسی فناوری اطلاعات
- مقطع تحصیلی
- کارشناسی ارشد
- محل دفاع
- کتابخانه مرکزی -تالار اطلاع رسانی شماره ثبت: 42567;کتابخانه مرکزی پردیس 2 فنی شماره ثبت: E 1623
- تاریخ دفاع
- ۱۰ آبان ۱۳۸۸
- دانشجو
- محمدرضا محمودی منش
- استاد راهنما
- ناصر یزدانی
- چکیده
- چکیده کیفیت اطلاعات (Quality of Information – QoI) در شبکه‌های حسگر بیسیم موضوع نسبتاً نوینی در حوزه شبکه‌های حسگر بیسیم است که سعی دارد رابطه‌ای میان عواملی مثل نرخ نمونه‌برداری و توپولوژی شبکه با دقت اطلاعات بازسازی شده از محیط بدست آورد. وجود یک رابطه ریاضی میان هزینه نمونه‌برداری و دقت اطلاعات بدست آمده، این امکان را می‌دهد که بتوان با اعمال تغییرات لازم بر پیکربندی شبکه با کمترین هزینه میزان دقت مطلوب را بدست آورد. شبکه حسگر بیسیم یک راه نمونه‌برداری توزیع شده است که در آن هزینه برداشت هر نمونه نسبتاً بالا است، چرا که علاوه بر هزینه گره حس کننده پارامتر فیزیکی، گرههای میانی شبکه نیز هزینه‌ای را جهت مخابره داده‌ها به مرکز ترکیب اطلاعات (Fusion Center) یا خروجی (sink) می‌پردازند. در خروجی با استفاده از داده‌های خام تجمیع شده، تصویری از وضعیت فعلی محیط به کاربر ارائه می‌شود. هدف اصلی مبحث کیفیت اطلاعات در شبکه‌های حسگر بیسیم این است که رابطه دقیقی را بین هزینه نمونه‌برداری و دقت بازسازی محیط بدست آورد. سپس با استفاده از این رابطه راهکاری ارائه می‌شود که با کمترین اتلاف انرژی گره‌ها، کیفیت مطلوب تصویر بازسازی شده از محیط بدست آید. نمونه‌برداری فشرده (Compressive Sampling a.k.a. Compressed Sensing) روش کلّی و کارایی را برای نمونه‌برداری از محیط‌هایی ارائه می‌دهد که در آن‌ها هزینه برداشت تک‌تک نمونه‌ها بالا است، با این شرط که آن سیگنال در یک دامنه دیگر مثل دامنه فوریه (Fourier domain) یا DCT تُنُک (sparse) باشد – به عبارت بهتر سیگنال قابل فشرده‌سازی باشد. سیگنال‌های طبیعی قابلیت فشرده‌سازی (compressibility) بالایی دارند و تقریباً همیشه فشرده‌سازی داده‌های خام ناشی از نمونه‌برداری از سیگنال‌های طبیعی (مثل صوت، دما و ... ) حجم اندکی از اطلاعات را نتیجه می‌دهد. نمونه‌برداری فشرده روشی را پیشنهاد می‌دهد که بر مبنای آن نمونه‌برداری به گونه‌ای صورت می‌گیرد که عمل بازسازی سیگنال اولیه از تعداد کاهش‌یافته‌ای از نمونه‌هایی که از یک ترکیب خطی نمونه‌های اصلی حاصل شده است، انجام می‌پذیرد. نمونه‌برداری فشرده سعی دارد عمل فشرده‌سازی را به لایه نمونه‌برداری نزدیک سازد و در آن ادغام نماید. «نمونه‌برداری فشرده بیسیم» پیاده‌سازی نمونه‌برداری فشرده در شبکه‌های حسگر بیسیم است و سعی دارد با کاهش نرخ نمونه‌برداری و داده‌های رد و بدل شده بین گرههای شبکه، هزینه بازسازی سیگنال محیط عملیاتی را کاهش دهد. تمرکز اصلی این پایان‌نامه بر نمونه‌برداری فشرده بیسیم به عنوان یک چارچوب همه‌جانبه و کارا برای کیفیت اطلاعات در شبکه‌های حسگر بیسیم است. آنچه در این پایان‌نامه به عنوان راهی برای بهبود کارایی نمونه‌برداری فشرده بیسیم معرفی می‌کنیم، ارائه مدلی هندسی از محیط عملیاتی است که با بازتعریف ترتیب گرههای حسگر، تصویری از سیگنال محیط به دست می‌دهد که قابلیت فشرده‌سازی بیشتری دارد. هرچه قابلیت فشرده‌سازی سیگنال محیط بیشتر باشد، نمونه‌های فشرده کمتری برای بازسازی محیط مورد نیاز خواهد بود. و در نتیجه نرخ نمونه‌برداری فشرده پایین خواهد که در نهایت به کاهش مصرف انرژی توسط گرههای حسگر می‌انجامد. نتایج آزمون‌های عددی این پایان‌نامه نشان می‌دهد که اگر تغییرات محیط در طول زمان خیلی شدید نباشد، می‌توان مدل هندسی بهبودیافته بدست آمده در یک بازه زمانی را برای بازه‌های آتی نیز بکار برد و انتظار داشت در بازه‌های بعدی نیز بهبود نمونه‌برداری فشرده بیسیم را در پی داشته باشد. اثبات می‌کنیم که محاسبه ترتیب بهینه نمونه‌برداری فشرده، یک مسأله NP-Complete است و در نتیجه نمی‌توان ترتیب کاملاً بهینه را در زمان چندجمله‌ای بدست آورد. اما یک الگوریتم تقریبی حریصانه را ارائه می‌نماییم که ترتیب بهینه را در زمان بدست می‌آورد که در آن n تعداد گرههای حسگر شبکه است. نتیجه مقایسه بین نمونه‌برداری فشرده بیسیم با و بدون استفاده از ترتیب‌د‌‌هی تقریباً بهینه (near-optimal) بدست آمده توسط الگوریتم تقریبی ما، نشان می‌دهد که می‌توان بین ?? تا ?? درصد نرخ نمونه‌برداری فشرده را کاهش داد و کیفیت اطلاعات را حفظ نمود و یا در نرخ نمونه‌برداری ثابت، کیفیت اطلاعات را به طرز محسوسی بهبود بخشید. کلمات کلیدی: نمونه‌برداری فشرده، شبکه‌های حسگر بیسیم، ترتیب نمونه‌برداری، مدل هندسی اقتضایی، سلول‌های ورونویی.
- Abstract
- Abstract Wireless Sensor Network (WSN) is an instance of a distributed spatial sampling problem in which we try to represent a virtual view of the operational environment using the data reported by the ad hoc sensory network. One factor that differentiates WSNs from other types of distributed sampling applications is that computational and communicational resources in WSN are very scarce. Therefore, all sampling schemes proposed for WSN aim to improve Quality of Information (QoI) while consuming as least energy as possible. In this thesis, we review models and frameworks devised for WSN to relate the effective factors such as topology of Sensor Nodes (SNs), energy consumption and spatial/temporal sampling rate to QoI. Finding such a relation helps us to design WSNs so that energy consumption is minimized while satisfying a minimum QoI or improving QoI consuming a predetermined amount of energy. Compressive Sampling a.k.a. Compressed Sensing (CS) promises a universal methodology for efficient sampling in situations where acquiring individual samples is expensive or limited. CS states that if a signal can be sparsely represented in a special domain such as Fourier domain, then it is possible to reconstruct the signal from fewer samples randomly selected from a linear transform of the actual signal. Compressive Wireless Sensing (CWS) is an implementation of CS in WSN which tries to reduce the data exchange between nodes while maintaining our ability to reconstruct the original signal from compressively sampled data. The main contribution of this thesis is proposing a geometrical spatial sampling model for WSN under which we can have a sparser representation of the signal. Signals sampled from natural events are expected to vary smoothly over time or space. In WSN where we can conventionally determine the order of samples, we may reorder the samples under a geometrical mapping to obtain a sparser signal. Our numerical experiments with a simulated synthetic operational environment, show that QoI stands better when CWS is applied with our improved reordering model.
