Manuscript ID : Visit : 11882 Page: -

Article Type: Original Research

Increasing the lifetime of underwater acoustic sensor networks by optimal relay node placement

Subject Areas : General

زهرا محمدی ¹ , محدثه سلیمان¬پور¬مقدم ² , داریوش عباسی¬مقدم ³ , سیامک طالبی ⁴

1 -
2 -
3 -
4 -

Accepted : 2020-04-21 Published : 2020-04-21

Keywords:

Abstract :

Underwater acoustic sensor networks (UASNs) have gained growing importance due to their desirable features and wide spread practical applications in many communication fields. Due to the high cost of underwater sensor nodes as well as implementation complexity, increasing the lifetime of UASNs is an important issue. Although relay nodes have an important role in reducing the transmission distance and energy consumption. But the efficient RNP (Relay Node Placement) to avoid the critical sensor nodes' elimination is the main problem, i.e., to preserve the connected network. For this aim this paper presents an innovative solution called an Efficient Relay node Setting (ERS) algorithm, which involves formulating the Relay Node Placement (RNP) as a non-convex optimization problem. Actually, due to the Difference Convex (DC) constraints the proposed RNP problem is a non-convex problem and finding an optimal solution is complicated. However, a novel transformation can be applied to DC constraints which converts the problem into its convex programming equivalent. Application of the convex programming offers the advantage of readily computing a global optimal solution. Simulation results confirm the superiority of the proposed scheme over the competing RA method in terms of network lifetime and efficiency.

References:

Full-Text:

دو فصلنامه علمي

فناوري اطلاعات و ارتباطات ایران

سال دوازدهم، شماره‌هاي 45 و 46، پاییز و زمستان1399

صص: 115_130

$E:\E Drive\logo\iicta Logo0.JPG$

بیشینهسازی طول عمر شبکههای حسگر صوتی زیرآبی با جایگذاری بهینه گرههای رله

زهرا محمدی* محدثه سلیمانپورمقدم** داریوش عباسیمقدم*** سیامک طالبی¹****

* کارشناس ارشد - گروه مهندسی برق - دانشگاه شهید باهنر کرمان

**استادیار - گروه مهندسی مکانیک - مجتمع آموزش عالی بم

***دانشیار - گروه مهندسی برق - دانشگاه شهید باهنر کرمان

****استاد - گروه مهندسی برق - دانشگاه شهید باهنر کرمان

تاریخ دریافت: 25/01/1399 تاریخ پذیرش: 06/09/1399

نوع مقاله: پژوهشی

چکیده

شبکههای حسگر صوتی زیرآبی به دلیل ویژگیهای مطلوب خود و کاربردهای عملی گسترده در زمینههای ارتباطی مختلف، توجه زیادی را به خود جلب کرده اند. از آنجا که گرههای حسگر زیرآبی دارای هزینهی بالا و پیچیدگی جایگذاری هستند، افزایش طول عمر این شبکهها از اهمیت زیادی برخوردار است. گرههای رله نقش مهمی در کاهش فاصله مخابراتی و انرژی مصرفی دارند. اما، مسئله مهم قرارگیری بهرهور گرههای رله اطراف گرههای بحرانی شبکه به منظور جلوگیری از حذف آنها و در نتیجه افزایش طول عمر شبکه است. برای این منظور، در این مقاله روشی جدید به نام جایگذاری بهرهور گره رله (ERS) معرفی شده است که شامل فرمولبندی کردن مکان هر گره رله به صورت یک مسئله بهینهسازی غیرمحدب است. در حقیقت، وجود قیود تفاضل محدب منجر به غیرمحدب شدن مسئله بهینهسازی پیشنهادی میشود و دستیابی به جواب بهینه را دشوار میسازد. از اینرو، در گام بعد با پیشنهاد یک تبدیل جدید، مسئله مذکور به معادل محدب خود تبدیل میشود. مهمترین مزیت مسئله برنامهریزی محدب، قابلیت دستیابی به جواب بهینه مسئله است. نتایج شبیهسازی نشاندهنده برتری عملکرد روش پیشنهادی در طول عمر و بهرهوری نسبت به روش ابتکاری پیشین تنظیم گره رله (RA) است.

واژگان کليدي: شبکههای حسگر صوتی زیرآبی، گرههای رله، طول عمر شبکه، مخابرات چندپرشی، برنامهریزی محدب.

[1] نویسنده مسئول: سیامک طالبیsiamak.talebi@uk.ac.ir

1. مقدمه

بخش اعظم سطح کره زمین با آب پوشیده شده است و کنترل آن حائز اهمیت است. با پیشرفت سریع فناوری شبکههای حسگر بیسیم، انگیزهای برای گسترش شبکههای حسگر صوتی زیرآبی ایجاد شده است [1]. شبکههای حسگر صوتی زیرآبی در مواردی مانند نظارت بر آلودگی، نظارت بر استخراج نفت و نظارت بر آبزیپروری

به کار برده میشوند، از اینرو، اخیراً بسیار مورد توجه قرار گرفتهاند [2, 3]. از جمله کاربردهای دیگر این شبکهها میتوان به اخطار سونامی، پیدا کردن لاشه کشتی، کاربردهای نظامی و امنیتی، اکتشاف منابع زیرآبی و غیره اشاره کرد. گرههای حسگر موجود در این شبکهها توانایی مشاهده محیط اطراف، جمعآوری اطلاعات از محیط، پردازش اندک اطلاعات جمعآوری شده و ارسال آنها را دارند. هر کدام از این اعمال باعث صرف انرژی میشود، البته اکثر انرژی در انتقال اطلاعات از دست میرود [4].

از آنجا که انرژی مصرفی گرههای حسگر از طریق یک باتری با انرژی محدود تامین میشود، این باتریها پس از مدتی تخلیه میشوند. با توجه به طبیعت محیط زیرآبی، امکان شارژ دوباره یا عوض کردن باتری گرههای حسگر زیرآبی وجود ندارد. بنابراین، اتمام انرژی گرهها علاوه بر ناکارآمدی آنها در نظارت بر محیط اطراف، منجر به عدم توانایی آنها در ارسال اطلاعات سایر گرههای حسگر در مخابرات چندپرشی¹ میشود. از سویی دیگر، هزینهی گرههای حسگر زیرآبی در مقایسه با گرههای حسگر زمینی بسیار بالا است و در نتیجه افزایش مدت کارکرد این گرهها مسئلهای مهم است [5].

ساخت یک شبکه حسگر زیرآبی چندپرشی در یک منطقه بزرگ چندین چالش را به دنبال دارد. برای مثال، گرههای حسگر نزدیک به ایستگاه پایه علاوه بر ارسال اطلاعات خود به سمت ایستگاه پایه مسئول ارسال اطلاعات بقیه گرههای حسگر هستند که موجب اتمام سریعتر انرژی آنها نسبت به سایر گرههای حسگر میشود. نویسندگان در [6] ثابت کردهاند زمانی که گرههای نزدیک به ایستگاه پایه تمام انرژی خود را از دست دادهاند، سایر گرهها 93% انرژی خود را حفظ کردهاند. این مسئله باعث ایجاد حفره انرژی² در شبکه و در نتیجه جزءبندی شدن شبکه میشود. در حقیقت، در یک شبکه جزءبندیشده بعضی از گرههای حسگر با وجود داشتن انرژی توانایی ارسال اطلاعات خود را به سمت ایستگاه پایه ندارند و در نتیجه طول عمر شبکه به پایان میرسد.

همانگونه که پیش از این بیان شد، هزینهی گرههای حسگر زیرآبی در مقایسه با همتای زمینی آنها بالاتر است، از اینرو جایگذاری آنها در محیط زیرآبی به صورت تنک³ انجام میشود [5]. جایگذاری تنک گرههای حسگر زیرآبی منجر به طولانی شدن فاصلهی مخابره⁴ بین آنها و در نتیجه افزایش انرژی مصرفی گرههای حسگر میشود. از آنجا که گرههای حسگر با توجه به الزامات پوشش⁵ و اتصال⁶ شبکه در منطقه هدف پراکنده میشوند، کاهش فاصله بین آنها به منظور کاهش انرژی مصرفی عملی نیست. از اینرو در [7, 8]، بکارگیری گرههای رله بزرگ و پرقدرت⁷ به منظور کاهش فاصله مخابراتی بررسی شده است. این گرهها دارای انرژی بیشتر و اندازه بزرگتر نسبت به گرههای حسگر هستند و به عنوان گرههای مسیریاب⁸ جهت ارسال اطلاعات گرههای حسگر به سمت ایستگاه پایه عمل میکنند. عیب بزرگ این گرهها اندازه بزرگ آنها است که در نتیجه به آسانی توسط دشمن قابل شناسایی هستند. بنابراین بکارگیری گرههای رله کوچک⁹ که دارای اندازه و انرژی یکسان با گرههای حسگر هستند از لحاظ عملی مناسبتر است [9].

در این مقاله جایگذاری گرههای رله کوچک در شبکه حسگر صوتی زیرآبی سهبعدی در نظر گرفته شده است. در حقیقت، از مشارکت گرههای رله جهت بهبود حفره انرژی و افزایش طول عمر شبکه حسگر زیرآبی استفاده شده است. علاوه بر آن، استفاده بهینه از انرژی گرههای رله مسئلهای است که در این تحقیق به آن پرداخته شده است. در ادامه، به دستهبندی مطالعات صورت گرفته در حوزه افزایش طول عمر شبکه حسگر صوتی زیرآبی پرداخته میشود.

عدهای از محققین روی طراحی پروتکل مسیریابی برای متعادل کردن مصرف انرژی بین گرههای حسگر متمرکز شدهاند. برای مثال، در [10, 11] به منظور افزایش طول عمر شبکه حسگر زیرآبی، فاصله بین گرههای حسگر و انرژی باقیمانده¹⁰ هر کدام به عنوان معیار برای انتخاب گرههای ارسالکننده به کار رفته است. دو پروتکل مسیریابی در [12] ارائه شده است، بر مبنای اولین روش پیشنهادی هر گره طبق انرژی باقیمانده خود به صورت تک یا چندپرشی با دیگر گرهها به مخابره اطلاعات میپردازد. همچنین، نویسندگان در پروتکل پیشنهادی دوم، با تخصیص انرژی بیشتر به گرههایی که مسئول حمل بار بیشتری در شبکه هستند سعی در رفع مسئله حفره انرژی در شبکه داشتهاند.

به هر حال، از آنجا که محیط زیرآبی غیر قابل پیشبینی است، طراحی یک پروتکل مسیریابی مناسب نیازمند پیچیدگی محاسباتی بالا است [13]. از این رو برخی رویکردهای کاهش مصرف انرژی حول نحوه جمعآوری اطلاعات از گرههای حسگر توسعه یافتهاند. به عنوان مثال، در [14, 15] جمعآوری داده مبتنی بر خوشهبندی¹¹ ارائه شده است، در این روشها کل گرههای حسگر به تعدادی خوشه تقسیم میشوند و در هر خوشه یک گره به عنوان سرخوشه¹² انتخاب میشود. پس از آن سرخوشهها مسئول ارسال اطلاعات سایر گرههای حسگر به سمت ایستگاه پایه میشوند. لازم به ذکر است در [14] بعد از انتخاب سرخوشهها، هر خوشه به زیرخوشههایی تقسیم میشود. در هر کدام از زیرخوشهها یک گره به عنوان گره نماینده، مسئول جمعآوری داده از دیگر گرهها میشود. همچنین در [15] انرژی باقیمانده و مکان گرههای حسگر به منظور انتخاب بهینه سرخوشهها در نظر گرفته شده است.

در شبکههای حسگر صوتی زیر آبی خطای ارسال تحت پیوندهای صوتی طولانی غیر قابل اجتناب است، از اینرو، در سالهای اخیر بحث کاهش احتمال خطا مورد توجه برخی از محققین قرار گرفته است. به منظور افزایش قابلیت اطمینان، ابتداییترین روش درخواست بازفرستی خودکار¹³ است [16]. اما از آنجا که این روش بر پایه ارسال دوباره اطلاعات هست، موجب توان مصرفی بالا در شبکه میشود. به همین منظور، نویسندگان در [17, 18] به بررسی روش تصحیح خطای رو به جلو¹⁴ به منظور افزایش طول عمر شبکه حسگر زیر آبی پرداختهاند. لازم به ذکر است که در روش تصحیح خطای رو به جلو مسئله بهینگی انرژی با بازفرستیهای بسیار کم قابل حل هست.

توجه به مسئله جایگذاری گره رله به منظور افزایش طول عمر شبکه حسگر صوتی زیرآبی در [19-22] بررسی شده است. در [19] به منظور کاهش انرژی مصرفی از حرکت گره رله بین دو گره در حال مخابره استفاده شده است. پس از پایان روند مخابره گرهها، گره رله به مکان اولیه خود بازمیگردد. همچنین به منظور جایگذاری گرههای رله در شبکه حسگر سهبعدی در [20] یک روش ابتکاری به نام تنظیم گره رله¹⁵ (RA) پیشنهاد شده است. طبق روش پیشنهادی ابتکاری RA، گرههای رله با توجه به یک تابع چگالی در مکانهای مختلف شبکه قرار میگیرند. بدین صورت که در مناطق با انرژی مصرفی بالاتر، تعداد بیشتری گره رله قرار میگیرد. اما در این روش مکان گرههای رله در دو گام به دست میآید به گونه ای که ابتدا مکان آنها روی سطح آب به صورت تصادفی تعیین میشود و سپس عمق آنها تنظیم میشود. این نوع روشهای جایگذاری ابتکاری دستیابی به مکان شبهبهینه را به دنبال دارد که باعث اتلاف منابع موجود میشود.

از سویی دیگر، برخی از نویسندگان با تعریف مسئله بهینهسازی ریاضی به جایگذاری گره رله در شبکه پرداختهاند [21, 22]. به عنوان مثال، روش پیشنهادی در [22] شامل یک مسئله بهینهسازی غیر محدب است. مسائل بهینهسازی غیر محدب دارای چندین نقطه بهینه محلی هستند و جواب مسئله به نقطه اولیه روشهای تکرار بستگی دارد، از اینرو پیدا کردن نقطه بهینه سراسری دشوار و گاهاً غیر ممکن است [23]. این عوامل منجر به زمانبر شدن و در نتیجه ناکارآمدی روش مطرح شده در [22] میگردد. به علاوه، نویسندگان در [21] ابتدا با در نظر گرفتن چیدمان دایروی برای قرارگیری گرههای حسگر، جایگذاری گره رله را به صورت همزمان با گرههای حسگر مورد مطالعه قرار دادهاند. با در نظر گرفتن این فرضیات و مدل سیستم، جایگذاری گره رله به صورت یک مسئله بهینهسازی دو هدفه¹⁶ شامل دو هدف متضاد فرمولبندی شده است. به منظور تبدیل مسئله دو هدفه به مسئله تک هدفه از روش مجموع وزنی¹⁷ استفاده شده است و در نهایت الگوریتم تفاضل محدب¹⁸ برای حل آن به کار رفته است. در این مقاله، با پیروی از [20] حالت کلیتر و عملیتری از جایگذاری گرههای حسگر (جایگذاری تصادفی) در نظر گرفته شده است. هدف اصلی، طراحی یک روش جایگذاری رله بر اساس مسائل بهینهسازی محدب است. در حقیقت، به دلیل برابر بودن جواب بهینه محلی با بهینه سراسری در مسائل بهینه سازی محدب، دستیابی به جواب بهینه بسیار سریعتر است. اما در عمل، بسیاری از مسائل به فرم غیر محدب هستند. در مواجه با این نوع مسائل، بهترین راهحل در صورت امکان تبدیل مسئله غیر محدب به همتای محدب آن است و در غیر اینصورت به دست آوردن جواب تقریبی مسئله از طریق تقریب محدب مسئله مورد توجه قرار گرفته است [24].

1-1 نوآوری و سازماندهی تحقیق

به طور کلی نوآوری مقاله به صورت زیر خلاصه میگردد:

1. با توجه به نقش مهم گرههای رله در افزایش طول عمر شبکه و به منظور غلبه بر چالشهای موجود در روشهای جایگذاری ابتکاری، هدف اصلی این مقاله به دست آوردن مکان بهینه گرههای رله در شبکههای حسگر صوتی زیرآبی است. جهت حصول به این هدف، در ابتدا با پیشنهاد الگوریتم «جایگذاری بهرهور گره رله¹⁹ (ERS)» مسئله جایگذاری گره رله به صورت یک مسئله بهینهسازی ریاضی فرمولبندی میشود. نکته حائز اهمیت، اعمال قید عملی به مسئله طرح شده است که قابلیت جایگذاری همزمان و غیرهمزمان گرههای رله با گرههای حسگر را به دنبال دارد. به بیانی بهتر، طبق روش پیشنهادی نه تنها حداکثر اتصال گره بحرانی با همسایگان عمق پایینتر آن تضمین میشود بلکه انرژی گره رله تا حد امکان ذخیره میگردد. قید مذکور به صورت یک قید خطی (با پیچیدگی پایین) به مسئله اضافه میشود.

2. با توجه به طبیعت غیرمحدب²⁰ مسئله طرحشده، دستیابی به مکان بهینه گرههای رله چالشبرانگیز است. طبق مطالعات صورت گرفته، در کارهای پیشین به بررسی بهینه جایگذاری گرههای رله پرداخته نشده است. از اینرو، در گام بعد با پیشنهاد یک تبدیل جدید مسئله پیشنهادی به معادل محدب خود تبدیل میشود. ویژگی مهم مسائل بهینهسازی محدب برابری بهینه محلی²¹ و بهینه سراسری²² آنها است، الگوریتمهایی که برای حل این مسائل توسعه یافتهاند از این ویژگی استفاده میکنند و بسیار سریع و کارا به جواب بهینه دست مییابند.

3. به منظور ارزیابی عملکرد روش پیشنهادی، به بررسی پیچیدگی زمانی و مقایسه طول عمر (از طریق آزمایشات شبیهسازی) با روش RA موجود در [20] پرداخته شده است. طبق بررسی انجام شده، پیچیدگی روش پیشنهادی همانند روش RA و طبق آزمایشات شبیهسازی عملکردی بالاتر از آن دارد.

ادامه این مقاله به صورت زیر سازماندهی شده است:

در بخش دوم، مدل سیستم ارائه میشود. روش پیشنهادی جایگذاری گره رله و مدل معادل محدب آن در بخش سوم به طور مفصل شرح داده میشود. در بخش چهارم، به صورت تحلیلی به بررسی بهرهوری روش پیشنهادی در برابر تغییرات محیط زیر آبی پرداخته میشود. بررسی پیچیدگی روش پیشنهادی و پس از آن نتایج ارزیابی روش پیشنهادی در بخش پنجم ارائه و تحلیل خواهند شد. در نهایت در بخش ششم، به جمع‌بندی این تحقیق پرداخته خواهد شد.

2. مدل سیستم

در این بخش به تشریح کامل شبکه حسگر صوتی زیرآبی سهبعدی پرداخته میشود. برای این منظور، ابتدا مدل سیستم و انرژی مصرفی مشخص میشوند، پس از آن تعریف طول عمر شبکه حسگر صوتی ارائه میشود. در انتهای بخش، به شرح فرضیات مورد استفاده در تحقیق پرداخته خواهد شد.

شبکه حسگر صوتی زیرآبی، سهبعدی و عمق محیط زیرآبیH در نظر گرفته میشود. منطقه هدف به صورت استوانه نشان داده شده در شکل 1 مدل میشود. شبکه دارای سه نوع گره شامل: گره حسگر، گره رله و ایستگاه پایه است. گرههای حسگر مسئول نظارت بر محیط اطراف و جمعآوری اطلاعات از آن هستند و هریک مجهز به فرستنده/گیرنده صوتی برای مخابرات تحت کانال زیرآبی هستند. اطلاعاتی که توسط هر گره حسگر جمعآوری میشود، باید به ایستگاه پایهی روی سطح آب برسد. هر گره حسگر علاوه بر جمعآوری اطلاعات از محیط اطراف، توانایی رله کردن اطلاعات سایر گرههای حسگر را دارد، در حقیقت اطلاعات گره حسگری که در فاصله زیاد از ایستگاه پایه قرار دارد با چندین پرش به آن میرسد. مکان گرههای حسگر در منطقه هدف به صورت تصادفی و مجموعه آنها با S مشخص میشود.

گرههای رله به عنوان گرههای مسیریاب بین گرههای حسگر عمل میکنند، مجموعه این گرهها با R مشخص میشود و هر یک مجهز به فرستنده/گیرنده صوتی برای مخابرات زیرآبی هستند. برخلاف گرههای حسگر که مکان آنها به صورت تصادفی تعیین میشود، مکان گرههای رله به صورتی دقیق برای بهبود عملکرد شبکه تعیین میشود. در این مقاله، گرههای رله به منظور افزایش طول عمر شبکه به آن اضافه میشوند. شایان ذکر است که از دیدگاه عملی، ابتدا مکان گرههای رله روی سطح آب ثابت میشود و سپس با استفاده از سیستم تنظیم عمق²³، عمق آنها معین میگردد [29]. هر دو نوع گره حسگر و رله دارای انرژی اولیه و برد مخابراتی هستند، بیانگر فاصله اقلیدسی بین دو گره و است و به صورت زیر محاسبه میشود:

در رابطه فوق، و به ترتیب مختصات دکارتی گره i و j است. در ادامه مدل انرژی مصرفی شبکه حسگر صوتی زیرآبی شرح داده میشود.

(1)

شکل 1. قرارگیری گرههای رله و حسگر در منطقه هدف استوانهای و دستگاه مختصات دکارتی

2-1- مدل انرژی مصرفی

مقدار انرژی که صرف مخابره اطلاعات و پردازش آن میشود، کل انرژی مصرفی یک گره را مشخص میکند. انرژی مصرفی ارسالی بین دو گره تابعی از فاصله بین دو گره، نرخ اطلاعات و همچنین ویژگیهای محیطی است [15]. به طور کلی مقدار انرژی که صرف ارسال یک بیت اطلاعات از گره i به سمت گره j میشود، با نماد مشخص میشود و از رابطه زیر قابل محاسبه است [15, 20]:

در رابطه فوق، انرژی مصرفی برای پردازش یک بیت اطلاعات جهت ارسال است، و به ترتیب نشاندهنده ضریب تقویتکننده ارسال در مدل فضای آزاد و چندمسیری هستند، همچنین، یک فاصله آستانه است. به طور خاص در رابطه با کانال زیرآبی، ضریب تقویتکننده برای هر دو مدل است [15, 20]، به طوریکه ضریب جذب در محیط زیرآبی است. در نتیجه، معادله مصرف انرژی برای ارسال یک بیت اطلاعات از گره i به سمت گره j به صورت زیر بازنویسی میشود:

(2)

ضریب جذب به فرکانس سیگنال صوتی (f) ربط دارد و برای فرکانسهای بالاتر از یک کیلوهرتز بر حسب از طریق رابطه زیر محاسبه میشود [25]:

(3)

لازم به ذکراست، این ضریب برای فرکانسهای پایینتر از یک کیلوهرتز به صورت زیر قابل بیان است:

(4)

در ادامه تعریف طول عمر شبکه حسگر صوتی زیرآبی ارائه میشود.

2-2- طول عمر شبکه

تعاریف متعددی برای طول عمر شبکههای حسگر صوتی زیرآبی وجود دارد، از جمله نویسندگان در [13, 20, 26] طول عمر شبکه را مدت زمان اتمام طول عمر اولین گره، تعریف کردهاند. در [27] دوره زمانی اتمام طول عمر همه گرههای شبکه را به عنوان طول عمر شبکه در نظر گرفتهاند. برخی دیگر آن را مدت زمان پایان طول عمر بخش مشخصی از گرهها در نظر گرفتهاند. با توجه به اینکه یک مخابره تا زمانی موثر و متعادل است که همه گرهها در شبکه موجود باشند [13]، بنابراین، طول عمر شبکه () مشابه [13, 20, 26] به صورت زیر تعریف میشود:

(5)

در رابطه فوق، طول عمر گره نوعی i است و از رابطه زیر قابل محاسبه است [20]:

(6)

لازم به ذکر است، انرژی مصرفی گره جهت دریافت یک بیت اطلاعات و بیانگر نرخ ارسالی از گره i به سمت گره j است. همچنین، انرژی باقیمانده گره i است. به منظور سهولت خوانندگان، لیست نمادهای مورد استفاده در مقاله در جدول 1 آورده شده است. فرضیات مورد استفاده در این مقاله در زیر ذکر شدهاند:

1. اتصال بین گرههای حسگر برقرار است و گرههای رله به منظور افزایش طول عمر شبکه به آن اضافه میشوند.

2. مکان گرههای حسگر و انرژی باقیمانده آنها معلوم است [20].

3. شبکه حسگر همگن فرض میشود و برد مخابراتی همه گرهها برابر است.

4. پهنای باند کانال صوتی زیرآبی محدود فرض میشود. این شرط از ظرفیت محدود لینک مشخصشده با نماد منعکس میشود. شرط محدود بودن پهنای باند کانال صوتی زیرآبی بیان میدارد که مجموع نرخ ارسالی از هر گره بایستی کمتر از باشد، بدین معنی که [20]:

(7)

(8)

با داشتن اطلاعات کامل از مدل سیستم، در ادامه به شرح روش پیشنهادی برای قرارگیری گرههای رله در شبکه پرداخته میشود.

جدول 1. لیست نمادها و تشریح آنها

3. روش پیشنهادی جایگذاری گرههای رله

همانگونه که پیش از این بیان شد، در این مقاله جایگذاری گرههای رله به منظور افزایش طول عمر شبکه مورد بررسی قرار گرفته است. طبق تعریف طول عمر شبکه در رابطه (6)، گرهای که دارای کمترین طول عمر است زمان کارکرد شبکه را مشخص میکند و به عنوان گره بحرانی²⁴ شناخته میشود. بنابراین، با قرار دادن گره رله اطراف گره مذکور طول عمر شبکه افزایش مییابد. برای این منظور، روش ERS برای تعیین مکان هر گره رله پیشنهاد میشود. همچنین، تعیین مکان دقیق گره رله تحت مسئله برنامهریزی محدب یکی دیگر از مباحثی است که در این مقاله به بررسی آن پرداخته شده است. در ادامه روش پیشنهادی به طور مفصل شرح داده میشود.

a. الگوریتم پیشنهادی ERS

گام اول برای جایگذاری گره رله، شناسایی گره بحرانی (تعیینکننده طول عمر شبکه) است، این گره به صورت مشخص میشود. بدین معنی که:

تشریح	نماد
مجموعه گرههای رله
مجموعه گرههای حسگر
برد مخابراتی گرههای حسگر و رله
نرخ ارسالی از گره به گره
انرژی باقیمانده گره
انرژی اولیه گرهها
مختصات گره
فاصله اقلیدسی دو گره و j
توان مصرفی برای ارسال یک بیت اطلاعات از گره به گره j
ضریب جذب محیط زیر آبی
فاصله آستانه
توان مصرفی برای پردازش یک بیت اطلاعات جهت ارسال
توان مصرفی برای پردازش یک بیت اطلاعات جهت دریافت
فرکانس سیگنال صوتی
طول عمر گره

همانگونه که از رابطه (3) برمیآید، مخابره هر گره با دورترین گره همسایه بیشترین انرژی را مصرف میکند. در روش پیشنهادی به این مسئله توجه شده است و به منظور افزایش طول عمر شبکه، گره رله در خط واصل گره بحرانی شبکه و دورترین همسایهاش قرار میگیرد و به عنوان گره مسیریاب بین آنها عمل میکند. بنابراین، در گام بعد دورترین همسایه گره به صورت زیر شناسایی و نامگذاری میشود:

(9)

به منظور افزایش طول عمر گره بحرانی ، گره رله در خط واصل گرههای و به صورت نشان داده شده در شکل 2 قرار میگیرد، از مزایای این نوع جایگذاری میتوان به موارد زیر اشاره کرد:

1. در این نوع جایگذاری، مطمئناً گره رله در برد مخابراتی دو گره حسگر و قرار میگیرد و توانایی مخابره با آنها را دارد.

2. نوع جایگذاری رله از نوع کارآمد است، بدین معنی که از مخابره گره رله در فاصلهای بیش از طول لینک جلوگیری میشود.

در صورتیکه بردار مکان گره نوعی j با نمایش داده شود (ایستگاه پایه واقع بر مبدا مختصات است)، با توجه به شکل 2 ارتباط با و به صورت زیر بیان میشود:

(10)

در رابطه فوق، فاصله اقلیدسی سهبعدی بین دو گره بحرانی و رله است. بنابراین، مختصات گره رله از طریق معادلات زیر به دست میآید:

(11)

(12)
(13)
(14)

شکل 2. قرارگیری گره رله در شبکه حسگر زیرآبی طبق روش پیشنهادی

واضح است اگر تنها هدف، بیشینهسازی طول عمر گره بحرانی b باشد گره رله روی آن منطبق میشود. با این نوع جایگذاری، گره رله مسئول مخابره با گره تحت فاصله طولانی میشود که منجر به بحرانی شدن وضعیت آن و در نتیجه ناکارآمدی جایگذاریاش میشود. خصوصاً در جایگذاری همزمان گرههای حسگر و رله که هر دو نوع گره دارای انرژی باقیمانده برابر (همان انرژی اولیه یا ) هستند انرژی مصرفی گرههای رله نیز از اهمیت خاصی برخوردار است. از اینرو، هدف اصلی روش پیشنهادی افزایش طول عمر شبکه حسگر زیرآبی و تضمین ارسال اطلاعات جمعآوری شده توسط گرههای حسگر به سمت ایستگاه پایه است. به بیانی دیگر، چنانچه گره بحرانی b توانایی ارسال اطلاعات دریافتی از گرههای همسایهاش را داشته باشد، اتصال او با آنها حفظ میشود. حال، مجموعه به صورت زیر تعریف میشود

که بیانگر کل گرههایی است که اطلاعات خود را به سمت گره ارسال میکنند. شایان ذکر است که اتصال همواره دو گره b و j در صورتی وجود دارد که

(15)

از جهت دیگر، طبق آنچه پیش از این بیان شد توجه به توان مصرفی گره رله از اهمیت خاصی برخوردار است. بنابراین، به منظور دستیابی به مکان گره رله، یک مسئله بیشینهسازی مقید در رابطه با طول عمر گره به صورت زیر پیشنهاد و طرح میشود:

(16)

مسئله فوق جزء مسائل بهینهسازی غیرمحدب در نظر گرفته میشود. این مسئله دارای تابع هدف محدب (بیان شده در (25))، قیود آفینی²⁵ (بیان شده در (26)- (27.ج))، قیود محدب (بیان شده در (28) و (29)) و تفاضل محدب²⁶ (قید (30)) است. وجود قید غیر محدب (31.د)، منجر به غیرمحدب شدن مسئله فوق میشود که حصول به مکان بهینه گره رله را دشوار میسازد. از اینرو، جهت غلبه براین چالش، در ادامه ابتدا فرم کلی این گونه مسائل شناخته و معرفی میشوند، سپس با پیشنهاد یک تبدیل جدید مسئله فوق به همتای محدب خود تبدیل میشود.

b. مسئله غیرمحدب جایگذاری گرههای رله و معادل محدب پیشنهادی

در این بخش، ابتدا گروه خاصی از مسائل غیرمحدب شامل تابع هدف محدب، قیود محدب (یا آفینی) و تفاضل محدب معرفی و شرح داده میشوند. بعد از آن با پیشنهاد و اعمال یک تبدیل جدید بر این مسائل، به معادل محدب آنها دست خواهیم یافت.

فرم کلی مسائل شامل تابع هدف محدب، قیود محدب و تفاضل محدب به صورت زیر فرمولبندی میشود:

(17)
	s.t.
(18)
(19)
(20)
(21)
(22)
(23)
(24)

به گونهای که x نشاندهنده بردار متغیرها و توابعی محدب یا آفینی هستند. همچنین، توابع تفاضل محدب هستند و به صورت زیر فرمولبندی میشوند:


	s.t.

(25)

همانگونه که از نام این نوع توابع مشخص است، دو تابع و محدب هستند و اصطلاحاً اجزای محدب تابع نامیده میشوند [28].

با پیشنهاد و معرفی متغیر جدید مسئله (25) به صورت زیر میتواند فرمولبندی شود:

(26)

همانگونه که پیش از این بیان شد، توابعی محدب هستند. همچنین، دو قید (32) و (33) که به صورت تفاصل یک تابع محدب ( یا ) و خطی () بیان شدهاند خاصیت تحدب را دارند (اثبات در پیوست آورده شده است). بنابراین جواب بهینه مسئله (34) با حل مسئله معادل محدب (20) به دست خواهد آمد.

اکنون با تعریف متغیر جدید tو اعمال تبدیل پیشنهادی فوق، مدل محدب پیشنهادی مسئله به صورت زیر حاصل میشود:

(27)
	s.t.
(28)
(29)
(30)

بنابراین، مسئله جایگذاری گره رله فوق به دسته مسائل برنامهریزی محدب تعلق دارد، در این مقاله برای حل آن از جعبه ابزار CVX موجود در نرم افزار متلب استفاده شده است.

4. بررسی بهرهوری روش پیشنهادی جایگذاری گره رله در برابر تغییرات محیط زیرآبی

به منظور حفظ کارایی شبکههای حسگر زیرآبی، گرههای زیرآبی بایستی نسبت به تغییرات شدید زیرآبی وضعیت پایداری داشته باشند. در حقیقت، تغییرات مکانی زیاد موجب خارج شدن گرهها از دید مخابراتی یکدیگر و مختل شدن کل شبکه حسگر میشود. در نتیجه این امر، نظارت بر محیط زیرآبی سخت و گاهاً غیر ممکن خواهد بود. برای این منظور تمهیداتی چون توسعه سخت افزار گرهها و استفاده از گرههای نیمه ساکن به جای گرههای شناور آزاد صورت گرفته است. بنابراین، تغییر مکان گرههای زیرآبی به صورت جزئی و در یک ناحیه محدود فرض میشود [30].

از آنجا که مکان گره نوعی i توسط سه مولفه مشخص میگردد، جابجایی مکانی آن به صورت قابل بیان است. بنابراین، ، و به ترتیب بیانگر تغییر مکان گره رله (r)، گره بحرانی (b)، دورترین همسایه گره بحرانی (f) هستند. از طرفی طبق روش پیشنهادی، مکان گره رله توسط سه رابطه (35)، (36) و (37) حاصل میشود. با در نظر گرفتن جابجایی هر یک از گرهها روابط مذکور به صورت زیر بازنویسی خواهند شد:


	s.t.








(31)

بگونهای که:

با توجه به همگن بودن شبکه حسگرصوتی زیرآبی (طبق فرض 3 مقاله) و قرارگیری سه گره f، b و r در برد مخابراتی یکدیگر (فاصله نسبتاً نزدیک)، میتوان بیان کرد:

(32)
(33)
(34)

(35)

حال میتوان گفت:

به طریق مشابه برای تغییرات صورت گرفته در قابل اثبات است. با جایگذاری شرط (45) و (46) در روابط (42)، (43) و (37) داریم:

بنابراین، با توجه به هندسه مسئله طرح شده و نکات عملی بیان شده، میتوان گفت که تغییرات مکانی تاثیر چندانی بر عملکرد روش پیشنهادی نخواهد داشت.

در ادامه به ارزیابی روش پیشنهادی جایگذاری گره رله (ERS) از لحاظ پیچیدگی و عملکرد پرداخته میشود و با روش ابتکاری RA موجود در [20] مقایسه میشود.

5. ارزیابی عملکرد

در این بخش ابتدا با تحلیل پیچیدگی زمانی روش پیشنهادی و پس از آن با ارائه و تشریح نتایج حاصل از شبیهسازی، به ارزیابی عملکرد روش پیشنهادی پرداخته میشود.

a. تحلیل پیچیدگی

مرسومترین روش برای به دست آوردن مرتبه پیچیدگی یک الگوریتم تعیین تعداد محاسبات آن شامل جمع، ضرب، تقسیم، جستجوی خطی و انتساب است. محاسبات روش پیشنهادی ERS در جدول 2 آورده شده است. اگر فرض شود که تعداد گرههای حسگر و رله برابر N و M باشد با توجه به جدول 1پیچیدگی روش پیشنهادی ERS به مرتبه زیر محدود میشود:

[1] Multi-hop communication

[2] Energy hole

[3] Sparse

[4] Transmission distance

[5] Coverage

[6] Connectivity

[7] Macro relay nodes

[8] Router nodes

[9] Micro relay nodes

[10] Residual energy

[11] Clustering

[12] Cluster head

[13] Automatic Repeat reQuest (ARQ)

[14] Forward Error Correction

[15] Relay node Adjusment

[16] Bi-objective optimization problem

[17] Weighted sum method (WSM)

[18] Difference Convex Algorithm

[19] Efficient Relay node Setting

[20] Non-convex

[21] Local optimum

[22] Global optimum

[23] depth adjustment system

[24] Critical node

[25] Affine constraints

[26] Difference convex

Rimag

Rimag is an integrated platform to accomplish all scientific journal requirements such as submission, evaluation, reviewing, editing, DOI assignment and publishing in the web.

Related Centers

Technical Support

Official pages

(36)

Share To

Article Url

Increasing the lifetime of underwater acoustic sensor networks by optimal relay node placement

Rimag

Links

Related Centers

Technical Support

Official pages