عنوان پایان‌نامه
جمع آوری داده در شبکه های سنسوری بی سیم با استفاده از رویکرد کدینگ منابع توزیع شده
- رشته تحصیلی
- مهندسی برق-مخابرات-سیستم
- مقطع تحصیلی
- کارشناسی ارشد
- محل دفاع
- کتابخانه مرکزی -تالار اطلاع رسانی شماره ثبت: 43850;کتابخانه مرکزی پردیس 2 فنی شماره ثبت: E 1689
- تاریخ دفاع
- ۰۶ بهمن ۱۳۸۸
- دانشجو
- حمیدرضا ارجمندی
- چکیده
- در این پایان¬نامه به بررسی مساله جمع¬آوری داده در شبکه¬های حسگر بی¬سیم با استفاده از کدینگ منابع توزیع شده می¬پردازیم. استفاده از کدینگ منابع توزیع شده امکان استفاده از وابستگی مکانی داده گره¬ها، برای کاهش نرخ ارسال گره¬ها را می¬دهد. در روشهای ارائه شده برای جمع¬آوری داده بر اساس کدینگ منابع توزیع شده عموما گره جمع¬کننده داده را بدون محدودیت منابع در نظر می¬گیرند. در حالی که اگر یک گره جمع¬کننده داده، خود یک گره معمولی شبکه باشد دارای محدودیت¬های حجم محاسبات و حافظه خواهد بود. علاوه بر این، در عمل کدینگ منابع توزیع شده کارآمد برای تعداد زیادی منبع دارای پیچیدگی زیادی است. بنابراین در این پایان¬نامه مساله جمع¬آوری داده کارآمد با یک گره جمع کننده داده که محدودیت پیچیدگی (محاسبات، حافظه و مرتبه محدود کدینگ منابع توزیع شده) دارد را در نظر می¬گیریم. برای این منظور ما یک ساختار تخصیص نرخ به گره¬ها ارائه می¬نمائیم که محدودیت¬های گره جمع¬کننده را در نظر می¬گیرد. بر اساس این ساختار مساله¬های مینیمم کردن هزینه کل شبکه و ماکزیمم کردن طول عمر شبکه را مطرح خواهیم کرد. برای حل این مسائل یک الگوریتم بر پایه برنامه¬ریزی پویا ارائه می¬کنیم که پیچیدگی حل مساله را نسبت به الگوریتم جستجوی کامل به طور قابل توجهی کاهش می¬دهد. همچنین برای کاهش پیچیدگی حل به مرتبه چند¬جمله¬ای، الگوریتمی زیربهینه اما همچنان کارآمد و نزدیک به بهینه ارائه خواهیم کرد¬. برای مساله ماکزیمم کردن طول عمر شبکه وقتی تنها محدودیت مرتبه کدینگ منابع توزیع شده در نظر گرفته شود، یک الگوریتم حریص بهینه با پیچیدگی محاسباتی چندجمله¬ای ارائه می¬کنیم. نتایج عددی نشان می¬دهند که الگوریتم¬های ارائه شده در مینیمم کردن هزینه شبکه و یا افزایش طول عمر. شبکه کارایی بالایی دارند. همچنین نتایج نشان می¬دهد که با استفاده از روشهای ارائه شده، حتی با محدودیتهای مذکور روی گره جمع¬کننده داده می¬توان تقریبا از همه وابستگی مکانی در دسترس میان گره¬ها استفاده نمود.
- Abstract
- In this thesis, we consider data gathering in wireless sensor networks (WSN) based on distributed source coding (DSC). Distributed source coding allows for exploiting the dependency between the nodes observations and reducing the required rate of communications. The particular focus of this thesis is on complexity constrained networks, where the storage and computational complexity of the data gathering node (DGN) is limited. This is of interest in WSNs with large number of nodes or when the DGN is simply a complexity limited sensor node which has been chosen as a cluster head. We propose a rate allocation structure, which takes into account the complexity constraints of the DGN. Based on this structure, we investigate the problem of rate allocation for the nodes to minimize the total cost or maximize the network lifetime. To this end, an optimal dynamic programming solution based on a trellis structure is proposed, which significantly reduces the computational complexity in comparison with a full search strategy. Also, a suboptimal yet high performance solution is presented, whose complexity grows in polynomial order with the number of network nodes. We also consider an alternate problem of maximizing network lifetime, where the DGN is not limited of storage, but employs a limited-order distributed source code (computational complexity constraint). To this end, an optimal greedy algorithm is proposed, whose complexity grows in polynomial order with the number of network nodes. The results show that the proposed algorithms provide efficient solutions to minimize the total cost or maximize the network lifetime in complexity constrained WSNs. Also, numerical results demonstrate that the presented solutions, even with limited complexity, allow for exploiting most of the available dependency and hence the achievable compression gain.
