ارائۀ روشی مبتنی بر هوش محاسباتی، برای بهبود مصرف انرژی در شبکه¬های هوشمند حسگر بی¬سیم
محورهای موضوعی :فائزه طالبیان 1 , حسن ختن¬لو 2 , منصور اسماعیل¬پور 3
1 - کارمند
2 - .دانشگاه آزاد واحد همدان؛پردیس تحصیلات تکمیلی علوم
3 - .دانشگاه آزاد واحد همدان؛پردیس تحصیلات تکمیلی علوم
کلید واژه: شبکه های هوشمندحسگر بی سیم, الگوریتم رقابت استعماری, تعادل انرژی, طول عمر شبکه,
چکیده مقاله :
پیشرفت های اخیر در زمینه الکترونیک و مخابرات بی سیم، توانایی طراحی و ساخت حسگرهایی را با توان مصرفی پایین، اندازه کوچک، قیمت مناسب و کاربری های گوناگون داده است. ظرفیت محدود انرژی حسگرها، چالش بزرگی است که این شبکه ها را تحت تاثیر قرار می دهد. خوشه بندی به عنوان یکی از روش های شناخته شده برای مدیریت این چالش استفاده می شود. برای یافتن مکان مناسب سرخوشه ها از الگوریتم رقابت استعماری که یکی از شاخه های هوش محاسباتی می باشد استفاده شده است. سرخوشه ها توسط مدل سه سطحي در ارتباط هستند، تا سرخوشه هايي با ظرفيت انرژي كم و دور از ايستگاه به عنوان سطح سوم شناخته شده و به طور غير مستقيم با ايستگاه پايه به تبادل اطلاعات بپردازد. اين موضوع باعث افزايش طول عمر شبکه های حسگر بی سیم مي شود
Recent advances in the field of electronics and wireless communication have given the ability to design and manufacture sensors with low power consumption, small size, reasonable price and various uses. The limited energy capacity of sensors is a major challenge that affects these networks. Clustering is used as one of the well-known methods to manage this challenge. To find the suitable location of the cluster heads, the colonial competition algorithm, which is one of the branches of computational intelligence, has been used. Cluster heads are connected by a three-level model, so that cluster heads with low energy capacity and far from the station are known as the third level and exchange information indirectly with the base station. This increases the lifespan of wireless sensor networks
.W.B. Heinzelman, A.P. Chandrakasan, and H. Balakrishnan, An application-specific protocol architecture for wireless microsensor networks. Wireless Communications, IEEE Transactions on, 2002. 1(4): p. 660-670.
2.R. Min, et al. Low-power wireless sensor networks. in VLSI Design, 2001. Fourteenth International Conference on. 2001: IEEE.
3.I.F. Akyildiz, et al., A survey on sensor networks. Communications magazine, IEEE, 2002. 40(8): p. 102-114.
4.A.A. Abbasi and M. Younis, A survey on clustering algorithms for wireless sensor networks. Computer communications, 2007. 30(14): p. 2826-2841.
5.J.N. Al-Karaki and A.E. Kamal, Routing techniques in wireless sensor networks: a survey. Wireless Communications, IEEE, 2004. 11(6): p. 6-28.
6.L. Subramanian and R.H. Katz. An architecture for building self-configurable systems. in Mobile and Ad Hoc Networking and Computing, 2000. MobiHOC. 2000 First Annual Workshop on. 2000: IEEE.
7.Z. Yong and Q. Pei," A energy-efficient clustering routing algorithm based on distance and residual energy for Wireless Sensor Networks. Procedia Engineering, 2012. 29: p. 1882-1888.
8.W.R. Heinzelman, A. Chandrakasan, and H. Balakrishnan. Energy-efficient communication protocol for wireless microsensor networks. in System Sciences, 2000. Proceedings of the 33rd Annual Hawaii International Conference on. 2000: IEEE.
9.A.M. Jasour, E. Atashpaz, and C. Lucas. Vehicle fuzzy controller design using imperialist competitive algorithm. in Second First Iranian Joint Congress on Fuzzy and Intelligent Systems, Tehran, Iran. 2008.
10.E. Atashpaz-Gargari and C. Lucas. Imperialist competitive algorithm: an algorithm for optimization inspired by
imperialistic competition. in Evolutionary Computation, 2007. CEC 2007. IEEE Congress on. 2007: IEEE.
11. S. Bayraklı, and S. Z.Erdogan. Genetic Algorithm Based Energ Efficient Clusters (GABEEC) in Wireless Sensor Networks, Procedia Computer Science 10, 247-254. 2012.
12.N.Enami, R .Askari Moghadam, K.Dadashtabar, M.Hoseini. Neural Network Based Energy Efficiency in Wireless Sensor Networks: a Survey’, In: International Journal of Computer Science & Engineering Survey (IJCSES) , Vol.1, No.1, August 2010, pp.39-55.
13.L.Shahvandi ,M.Teshnehlab, and A.Haroonabadi. A Novel Clustering in Wireless Sensor Networks used by Imperialist Competitive Algorithm, 2011.
فصلنامه علمي- پژوهشي فناوري اطلاعات و ارتباطات ایران | سال هفتم، شماره‌هاي 23 و 24، بهار و تابستان 1394 صص: 25- 36 |
|
ارائۀ روشی مبتنی بر هوش محاسباتی، برای بهبود مصرف انرژی در شبکههای هوشمند حسگر بیسیم
*فائزه طالبیان **حسن ختنلو ** منصور اسماعیلپور
*گروه مهندسی کامپیوتر، واحد همدان، دانشگاه آزاد اسلامی، همدان، ایران
** هیئت علمی، دانشگاه بوعلی سینا همدان، همدان، ایران
***گروه مهندسی کامپیوتر، واحد همدان، دانشگاه آزاد اسلامی، همدان، ایران
تاریخ دریافت: 16/10/92 تاریخ پذیرش:25/03/94
چکيده
پیشرفت های اخیر در زمینه الکترونیک و مخابرات بی سیم، توانایی طراحی و ساخت حسگرهایی را با توان مصرفی پایین، اندازه کوچک، قیمت مناسب و کاربری های گوناگون داده است. ظرفیت محدود انرژی حسگرها، چالش بزرگی است که این شبکه ها را تحت تاثیر قرار می دهد. خوشه بندی به عنوان یکی از روش های شناخته شده برای مدیریت این چالش استفاده می شود. برای یافتن مکان مناسب سرخوشه ها از الگوریتم رقابت استعماری که یکی از شاخه های هوش محاسباتی می باشد استفاده شده است. سرخوشه ها توسط مدل سه سطحي در ارتباط هستند، تا سرخوشه هايي با ظرفيت انرژي كم و دور از ايستگاه به عنوان سطح سوم شناخته شده و به طور غير مستقيم با ايستگاه پايه به تبادل اطلاعات بپردازد. اين موضوع باعث افزايش طول عمر شبکه های حسگر بی سیم مي شود.
واژههای کلیدی: شبکه های هوشمندحسگر بی سیم، الگوریتم رقابت استعماری، تعادل انرژی، طول عمر شبکه.
1- مقدمه
پیشرفت تکنولوژی مخابرات و صنعت قطعات الکترونیکی و الکتریکی، منجر به ساخت حسگر های کوچک و نسبتاً ارزان قیمت شده که از طریق یک شبکه بی سیم با یکدیگر در ارتباط هستند[1]. این حسگرهای که توانایی انجام اعمالی چون، دریافت اطلاعات از پیرامون خود، پردازش و ارسال آن اطلاعات دارند و موجب پیدایش شبکه های حسگرها بیسیم
حسگرها بی سیم شده اند، این شبکه ها که کنترل از راه دور را ایجاد می کنند، اساساً شبکه های جمع آوری داده هستند. کاربر نهایی ایستگاه نیازمند توصیف سطح بالایی از محیطی است که حسگرها در آن قرار گرفته اند[2].
نویسنده عهدهدار مکاتبات : فائزه طالبیان talebiean.faezeh32@yahoo.com |
در پروتکل های سلسله مراتبی مبتنی بر خوشه بندی، شبکه به چند دسته تقسیم می شود، به این دسته ها خوشه می گوییم. هر خوشه دارای یک سرخوشه می باشد که وظیفه جمع آوری داده ها از زیر خوشه های خود را دارد و داده های تجمیع و ترکیب شده را به ایستگاه پایه ارسال می کند. که به طور قابل توجهی مصرف انرژی را کاهش می دهد و طول عمر شبکه را زیاد می کند[5]. خوشه بندی یک راه طبیعی برای گروه بندی گره های نزدیک به هم و حذف داده های افزونه است[6].
این مقاله برای شبیه سازی شبکه های هوشمند حسگر بی سیم پروتکل DECSAرا پیشنهاد می کند. این پروتکل در محیط های وسیع کاربرد دارند و از ارتباط مستقیم سرخوشه هایی که از ایستگاه دور هستند، جلوگیری می کند. با توجه به اینکه در هر دوره باید مناسب ترین حسگر به عنوان سرخوشه از میان تعداد زیادی حسگر انتخاب شود از الگوریتم رقابت استعماری که روشی هوشمندانه است استفاده شده است. انتخاب مناسب مکان سرخوشه تاثیر بسیاری در بهبود مصرف انرژی و افزایش طول عمر این شبکه ها دارد.
در ادامه به معرفي پروتكل سه سطحي سلسه مراتبي DECSA و پروتكل رقابت استعماري پرداخته شده، در بخش 2، الگوريتم پيشنهادي و مراحل آن معرفي شده، در بخش 3، به بررسي و مقايسه شبيه سازي الگوريتم پيشنهادي با الگوريتم هاي مشابه پرداخته شده و در انتها در بخش 4، نتيجه گيري بيان شده است.
1-1- پروتکل DECSA
پروتکل LEACH از مکان و انرژی باقیمانده حسگرها اطلاع ندارد و در نتیجه باعث مرگ حسگرها می شود. او انرژی همه حسگرها را یکسان تصور می کند. پروتکل DECSA مبتنی بر پروتکل خوشه بندی کلاسیک LEACH است، ولی انرژی باقیمانده و فاصله را تاثیر می دهد. به همین دلیل این پروتکل توانسته است به خوبی بار انرژی را در شبکه به طور یکنواخت توزیع کند. در نتیجه باعث بهبود پردازش انتخاب سرخوشه و شکل خوشه بندی می شود. این پروتکل از ارتباط مستقیم ایستگاه پایه و سرخوشه ها جلوگیری می کند، زیرا توزیع غیر یکنواخت حسگرها در محیط ممکن است سرخوشه ایی از ایستگاه اصلی دور و انرژی باقیمانده آن نیز کم باشد[7].
مدل انرژی
مقداری انرژی، برای ارسال و دریافت بسته های داده، از منبع انرژی حسگر کم می شود. مقدار انرژی لازم براي ارسال و دريافت بسته ها، براساس رابطه های زیر می باشد که با مدل انرژی هاینیزلمن [8] یکسان می باشد.رابطه (1)، E TX مقدار انرژی مصرفی برای ارسالی یک بیت داده در فاصله d را نشان می دهد.
(1) 
رابطه (2)، E RX مقدار انرژی دریافتی برای دریافت یک بیت داده در فاصله d را نشان می دهد.
(2) 
در روابط بالا، Eelec : مقدار انرژی مورد نیاز، در مدار الکترونیکی گیرنده یا فروشنده جهت دریافت یا ارسال یک بیت از بسته داده می باشد. emp: انرژی مصرف شده در تقویت کننده رادیویی مي باشد. L: طول بسته ارسال شده می باشد،efs : انرژی مصرف شده در تقویت کننده رادیویی برای فضای آزاد مي باشد، d: طول کانال بین حسگر فروشنده و حسگر گیرنده مي باشد. d0 : یک فاصله ی آستانه برای مدل آزاد است که مقدار آن 7/87 متر می باشد.
مدل شبکه
ما فرض می کنیم گره های حسگر به صورت تصادفی در محیط مربعی شکلی پخش می شوند. کلیه عملیات خوشه بندی در ایستگاه پایه انجام و به گره های سرخوشه اطلاع داده می شود. آن ها نیز با ارسال پیام گره های دیگر را مطلع می کنند. مدل DECSA یک ساختار سلسله مراتبی سه سطحی را بیان می کند.گره های حسگر به چهار طبقه تقسیم می شوند كه عبارتند: ایستگاه پایه (BS)، سرخوشه ایستگاه پایه (BCH)، گره سرخوشه (CH) و گره حسگر معمولی (SN).
شکل 1 : مدل شبکه DECSA
این پروتکل مانند LEACH زمان را به قسمت هایی با طول مساوی به نام دور (Round) تقسیم می کند. هر دوره نیز به دو فاز تقسیم می شود، فاز اول که فاز راه اندازی نام دارد و فاز تشکیل خوشه ها می باشد. فاز دوم، فاز حالت پایدار نامیده می شود که مربوط به انتقال اطلاعات است.
فاز راه اندازی
در این حالت سرخوشه انتخاب می شود. همه گره های حسگر معمولی به یک سرخوشه متصل می شوند. انتخاب سرخوشه از دو بخش تشکیل شده است. 1-انتخاب گره سرخوشه (CH) و 2-انتخاب سرخوشه ایستگاه پایه (BCH). در انتخاب CH براساس انرژی باقیمانده و فاصله است. ابتدا هر گره حسگر عدد تصادفی را بین صفر و یک تولید می کنند. اگر عدد تصادفی کمتر از آستانه T باشد، آن اولین سرخوشه می باشد.
بعد از گره سرخوشه ها (CH) باید سرخوشه ایستگاه پایه (BCH) را انتخاب شود. برای گره سرخوشه های (CH) رابطه (3) محاسبه می شود. از میان گره سرخوشه (CH) آنهایی به عنوان سرخوشه ایستگاه پایه (BCH) انتخاب می شود که بزرگترین 
را داشته باشند و بقیه سرخوشه ها به عنوان گره سرخوشه (CH) باشند.
(3) TBCE(i) = ( En(i) / E0 ) + ( En(i) / d(i) )
در بالا 
: انرژی باقیمانده گره i است، E0 : انرژی ابتدایی گره های حسگر مي باشد، d(i) : فاصله بین گره i تا ایستگاه پایه مي باشد.
فاز حالت پایدار
یک حسگر معمولی (NS) بسته داده را به نزدیکترین سرخوشه ارسال می کند و پس از آن گره سرخوشه (CH) داده ها را تجمیع و ترکیب می کند و آن را به جای اینکه مستقیم به ایستگاه پایه (BS) ارسال کند، به سرخوشه ایستگاه پایه (BCH) ارسال می کند. اگر سرخوشه خودش از نوع ایستگاه پایه(BCH) باشد خودش بسته داده را مستقیم به ایستگاه پایه (BS) ارسال می کند.
1-2- الگوریتم رقابت استعماری
الگوریتم رقابت استعماری( Imperialist competitive Algorithm) که به اختصار به آن ICA گفته می شود یکی از جدیدترین الگوریتم بهینه سازی هوشمند در حوزه هوش محاسباتی است. این الگوریتم شبیه سازی فرآیند سیاسی استعمار است و در آن از تکامل سیاسی استفاده شده است. این الگوریتم در کاربردهای فراوان و زمینه های مختلف به عنوان ابزار بهینه سازی مورد استفاده قرار گرفته است. به طور خلاصه مراحل این الگوریتم توضیح داده می شود[9],[10].
جمعیت اولیه این الگوریتم با ساخت چند کشور اولیه شروع به کار می کند. کشورها به دسته هایی به نام امپراتوری تقسیم می شوند.
هر امپراتوری از تعدادی مستعمره و یک امپریالیست تشکیل شده است. کشور اولیه را به تعداد N country تولید می کنیم، تعداد Nimp از کشورهای اولیه امپریالیست هستند و باقیمانده کشورها به تعداد Ncol مستعمره می شوند.
هر کشور، یک آرایه (ساختار) N بعدی است که دارای N تا خصوصیت می باشد. در يک مسئله‌ي بهينه‌سازي 
بعدي، يک کشور، يک آرايه‌ي 
است. اين آرايه به صورت زير تعريف مي‌شود.
(4) Country = [ P1 , P2 , P3 , …, P N]
تابع هزینه این الگوریتم نیز مانند سایر الگوریتم های هوش محاسباتی دارای یک تابع هزینه است. توسط این تابع هزینه هر کشور را محاسبه می کنیم. هزينه‌ي يک کشور با ارزيابي تابع 
در متغير‌هاي (P1 , P2 , P3 , …, P N ) يافته مي‌شود. بنابراين
(5) Costi = ƒ( countryi ) = ƒ(P1 , P2 , P3 , …, P N )
ساخت امپرالیست در این مرحله از الگوریتم براساس تابع هزینه، کشور ها را دسته بندی می کنیم. به تعداد Nimpتا از بهترين اعضاي اين جمعيت (کشورهاي داراي کمترين مقدار تابع هزينه) را به عنوان امپرياليست انتخاب مي‌کنيم و Ncol تا از کشورها، مستعمره را تشکيل مي‌دهند. به هر امپرياليست، تعدادي مستعمره متناسب با قدرت آن، داده می شود.
سیاست جذب کشورهای استعمارگر با اعمال سیاست جذب در راستای محورهای مختلف بهینه سازی، کشور مستعمره را به سمت خود می کشد. قدرت کل هر امپراتوری تشکیل شده از قدرت کشور استعمارگر، به اضافه ی درصدی از میانگین قدرت مستعمرات آن است.
T.C = Cost(imperialist) + (6)
ξ mean{ Cost(colonies of empire) }
کشور مستعمره به اندازه x به سمت استعمارگر حرکت می کند. بهتر است این حرکت به اندازه 
انحراف داشته باشد. x و عدد تصادفی با توزیع یکنواخت هستند که در میانگین قدرت ضرب می شوند .
(7) X ~ U( 0,β×d )
(8) ) θ ~ U( - γ , γ
انقلاب این مرحله مشابه جهش، در الگوریتم ژنتیک است. کشورهای داخل یک امپرالیست به صورت تصادفی انقلاب می کنند، تا به شرایط و موقعیت های بهتری دست یابند و به قدرت بیفزاید. هر امپراطوري‌اي که نتواند بر قدرت خود بيفزايند، در جريان رقابت‌هاي امپرياليستي، حذف خواهد شد.
رقابت درون گروهی این رقابت در درون امپراتوری انجام می گیرد. در حین حرکت مستعمرات به سمت کشور استعمارگر و انقلاب ممکن است، بعضی از این مستعمرات به موقعیتی بهتر از استعمار گر دست یابند. در این صورت کشور استعمارگر و کشور مستعمره ، جای خود را عوض می کنند.
رقابت بیرون گروهی هر امپراطوري‌اي که نتواند بر قدرت خود بيفزايد، در جريان رقابت‌هاي امپرياليستي، حذف خواهد شد. بدين معني که به مرور زمان، امپراطوري‌هاي ضعيف، مستعمرات خود را از دست داده و امپراطوري‌هاي قويتر، اين مستعمرات را تصاحب کرده و بر قدرت خويش مي‌افزايند. در ابتدا ضعیف ترین مستعمره ضعیف ترین کلونی را از دست می دهد.
1-3- تعداد خوشه ها
در خوشه بندي تعداد خوشه ها بايد از تعداد داده ها کمتر باشند. مزیت خوشه بندی سلسله مراتبی این است که به استفاده کننده و تحلیل گر اجازه می دهد، که از بین حالات مختلف یک عدد برای تعداد خوشه ها انتخاب نماید. سوالی که همیشه مطرح است چه تعداد خوشه مناسب است؟ در رابطه (9) مقدار K بیانگر تعداد بهینه خوشه ها می باشد[8].
(9) 
K = 
(10) 75< d toBs < 185
برای شبکه ایی که شامل N= 100 گره حسگر توزیع شده در یک ناحیه M × Mکه مقدار m100M= باشد 
و 
باشد و فاصله محدوده آزاد d toBs تعیین می کند، آنگاه تعداد بهینه سرخوشه رابطه (11) می باشد.
(11) 6 1 < K <
2- الگوریتم پیشنهادی
در روش پیشنهادی ما فرض شده، تمام گره های حسگر یکسان هستند و به صورت تصادفی در محیط پخش شده اند. کلیه عملیات تشکیل و مدیریت خوشه ها در ایستگاه پایه انجام می گیرد. هر حسگر سه حالت می تواند داشته باشد: گره سرخوشه ایستگاه پایه (BCH)، گره سرخوشه (CH) و گره معمولی (SN).
اين الگوريتم از دو فاز تشكل شده است. در فاز راه انداز بهترين سرخوشه به كمك الگوريتم استعماري پيدا مي شود و در فاز حالت پايدار انتقال اطلاعات از حسگر به ايستگاه پايه صورت مي گيرد.
در ابتدا جمعیت اولیه را به نام کشور می سازیم. هر کشور دارای تعدادی سرخوشه می باشد که به عنوان یک خصوصیت برای آن مطرح می شود. خصوصیت دیگر کشور، هزینه سرخوشه ها می باشد. هزینه کشورها به روش زیر محاسبه می شود. رابطه (12) نشان دهنده تابع هزینه سرخوشه است، که به صورت زیر تعریف می شود.
(12) 
که 
: انرژی باقیمانده گره سرخوشه i است، d0(i) : میانگین فاصله سرخوشه i تا کل گره های زیر خوشه اش می باشد و به صورت زیر تعریف می شود.
(13) 
در رابطه بالا 
: تعداد خوشه iام است. تابع f در رابطه (14) نشان دهنده هزینه هر کشور است. هزینه هر کشور حاصل جمع خصوصیات کشور (هزینه سرخوشه های) آن است.K: تعداد خوشه های تعیین شده برای شبکه می باشد.
(14) 
در این فرمول کمترین هزینه، بهترین سرخوشه است. هزینه هر کشور با هزینه سرخوشه ها رابطه مستقیم دارد. در نتيجه كشوري با هزينه سرخوشه هاي كمتر، بهترين كشور شناخته مي شود. کشورهایی که کمترین تابع هزینه را دارند، به تعداد Nimp به نام استعمارگر در نظر گرفته مي شود. کشورهای باقیمانده بر اساس چرخ رولت به عنوان مستعمره امپرالیست ها، بين استعمارها پخش می شوند.
در هر دوره کشورهای استعمارگر سعی در جذب و هم گون سازی، کشورها تحت تسلط خود را دارند. به همین ترتیب تغییراتی را در ساختار آنها ایجاد می کنند. کشورهای مستعمره هم چنین با انجام انقلاب سعی به بهبود قدرت کشورشان دارند و برای رسیدن به قدرت استعماگر تلاش می کنند. عمل همگون سازی و انقلاب هر کشور، تغییر دادن سرخوشه هایش و پیدا کردن سرخوشه ایی بهینه تر، با هزینه کمتر است. در نتیجه ممکن است هزینه کشور مستعمره کمتر از استعمارگر شود که در این صورت باید جای این دو کشور با هم عوض شود. چندین مرحله رقابت در بین کشورها انجام می شود. آخرین مرحله، قدرتمندترین استعمارگر از لحاظ موقعیت در شبکه بهترین سرخوشه را دارد. در فاز راه اندازی شبکه بهترین سرخوشه توسط الگوریتم رقابت استعماری مشخص شده است. در فاز حالت پایدار براي تمام سرخوشه ها مقدار TBCH محاسبه مي شود.
(15) TBCE(i) = ( En(i) / E0 ) + ( En(i) / d(i) )
مقدار 75% سرخوشه هايي كه TBCH بزرگتري دارند، را به نام گره سرخوشه پایه (BCH) نام گذاري و ساير سرخوشه ها به نام گره سرخوشه (CH) نام گذاري مي شود.
شکل2: شمای کلی الگوریتم پیشنهادی |
شکل 3 : انتخاب نوع سرخوشه
شکل 4 : مسیر انتقال بسته داده در الگوریتم پیشنهادی
جدول 1: پارامترهای شبیه سازی
Value | Parameters |
50*50, 200*200m | Network Size |
100 | Node Number(N) |
( 50,150 )m | Sink Coordination |
0.5 J & 0.25J | Initial Energy |
50 nj/bit | E TX = ERX |
87 m | D0 |
5 nJ/bit/signal | E DA |
2000 Bytes | Packet Length |
شکل 5 : مقایسه الگوریتم پیشنهادی از لحاظ کارایی
پس از شناسايي نوع سرخوشه؛ گره حسگر معمولی (SN) بسته داده را به گره سرخوشه (CH) خودش ارسال می کند سرخوشه باید داده های رسیده را ترکیب و تجمیع کند. اگر سرخوشه یک گره سرخوشه (CH) بود داده را به نزدیکترین گره سرخوشه پایه (BCH) ارسال می کند در غیر این صورت خود مستقیم داده را به ایستگاه پایه ارسال می کند. مقدار انرژي مورد نياز در هر ارسال و دريافت داده در سرخوشه و حسگر محاسبه مي شود و از انرژي باقيمانده حسگر كاسته مي شود.
3- شبیه سازی
شبیه سازی الگوریتم پیشنهادی با پارامترهای نشان داده شده در جدول(1)صورت گرفته است.
الگوريتم هاي مختلفي براي خوشه بندي استفاده شده است. هدف اين الگوريتم ها بهبود طول عمر شبكه هاي حسگر بي سيم مي باشد. الگوريتم LEACH جز اولين الگوريتم هاي خوشه بندي مي باشد. در روش هاي ديگر، براي يافتن مكان سرخوشه ها از الگوريتم هوش محاسباتي استفاده مي كنند؛ مانند الگوريتم GABEEC [11] كه براي يافتن مكان سرخوشه ها از الگوريتم ژنتيك استفاده كرده است. در شكل (5) به مقايسه کارایی الگوريتم پيشنهادي با الگوریتم LEACH وGABEEC [12] پرداخته شده است.
هر سه الگوريتم در محيط مربعي شكلي با ابعاد m50m×50 با 100حسگر مورد مقايسه قرار گرفته اند. همان طور كه مشخص است، عملكرد الگوريتم از نظر افزايش طول عمر شبكه نسبت به دو الگوریتم LEACH وGABEEC بهبود يافته است. الگوریتم ارائه شده زمان مرگ اولين گره را به صورت قابل توجهي در مقایسه با دو الگوریتم دیگر افزايش داده است.
این شبیه سازی در دو مرحله با دو مقدار انرژی اولیه، یک بار E=0.25J و در مرحله دیگر با E=0.5J صورت گرفته است. حاصل این شبیه سازی در شکل(6و 7) قابل مشاهده است. در این شکل زمان مرگ اولین و آخرین گره با هم مقایسه شده است.
در شكل(8)، الگوريتم براي محيط وسيعي با ابعاد m200m×200 در نظر گرفته شده است. در الكوريتم پيشنهادي مرگ اولين گره در دوره زماني 879 و مرگ آخرين گره حسگر در دوره زماني2110 اتفاق افتاده است. در صورتي كه الگوريتم LEACH مرگ اولين گره اش در دوره زماني 196 صورت گرفته است.
از آن جايي كه از دست دادن گره‌هاي حسگر فعال در ناحيه‌اي از شبكة حسگر، با از دست رفتن پوشش شبكه‌اي، پايش آن ناحيه را غير‌ممكن خواهد ساخت، حفظ پوشش شبكه‌اي يكي از مهمترين معيارهاي ارزيابي الگوريتم‌هاي مسيريابي شبكة حسگر محسوب مي‌گردد. در شكل (9) پوشش شبكه‌اي روش پبشنهادی و LEACH ( 50گره مرده از 100 گره اوليه) مورد مقايسه قرار گرفته اند. مكان ايستگاه مبنا در اين حالت (x=50, y= 200) در نظر گرفته شده است. مقايسه تعداد(درصد) نواحي زنده در دو الگوريتم حاكي از آن است كه LEACH، 56% و الگوریتم ICA & DECSA، 96% پوشش شبكه‌اي خود را در زمان مرگ نيمي از گره‌هاي شبكه حفظ كردند. بنابراين40% افزايش در پوشش شبكه‌اي را نسبت به LEACH از خود نشان مي‌دهد.
نتایج شبیه سازی نشان می دهد که پروتکل DECSA به همراه الگوریتم ICA توانسته اند مصرف انرژی برای شبکه های حسگر بی سیم کاهش بدهند و طول عمر شبکه را افزایش بدهند.
4- نتیجه گیری
شبکه حسگر بی سیم، محیطی هوشمند را در سطح منطقه ایجاد می کنند. اين شبکه ها، داده ها را از کل منطقه تحت پوشش جمع آوری و به ایستگاه پایه اطلاع رسانی می کنند. مصرف بهینه انرژی حسگرها نقش موثری در بقا این شبکه ها دارند. خوشه بندی به عنوان یکی از روش های شناخته شده برای مدیریت مصرف بهينه انرژي استفاده می شود.
در اين مقاله از خوشه بندي استفاده شده و براي يافتن بهترين سرخوشه ها از نظر مكان و انرژي باقيماند، از الگوریتم رقابت استعماری که یکی از شاخه های هوش محاسباتی می باشد استفاده شده است. كارهاي بسياري با ساير شاخه هاي هوش محاسباتي در اين زمينه صورت گرفته شده است [13-12].
شکل 6: انرژی اولیه E=0.5J
شکل 7: انرژی اولیه E=0.25J
شكل(8): طول عمر شبکه
ب: الگوریتم پیشنهادی |
الف: الگوریتم LEACH |
شکل 9 : مقایسه الگوریتم پیشنهادی از لحاظ پوشش شبكه‌اي
خوشه ها توسط مدل شبکه سلسله مراتبی سه سطحي، در ارتباط هستند، تا سرخوشه هايي با ظرفيت انرژي كم و دور از ايستگاه به عنوان سطح سوم شناخته شده و به طور غير مستقيم با ايستگاه پايه به تبادل اطلاعات بپردازد. تبادل اطلاعات با سطح دوم باعث حفظ انرژي آن سرخوشه شده و از مرگ سريع و نامتقارن در شبكه جلوگيري مي كنند. در نتیجه این سرخوشه ها انرژی کمتری در مقایسه با پروتکل های شبکه مصرف می کند.
بنابر مسائل مطرح شده و نتايج شبيه سازي، الگوریتم پیشنهادی توانسته است باعث بهبود مصرف انرژی در شبکه های حسگر بی سیم شود.
منابع
1.W.B. Heinzelman, A.P. Chandrakasan, and H. Balakrishnan, An application-specific protocol architecture for wireless microsensor networks. Wireless Communications, IEEE Transactions on, 2002. 1(4): p. 660-670.
2.R. Min, et al. Low-power wireless sensor networks. in VLSI Design, 2001. Fourteenth International Conference on. 2001: IEEE.
3.I.F. Akyildiz, et al., A survey on sensor networks. Communications magazine, IEEE, 2002. 40(8): p. 102-114.
4.A.A. Abbasi and M. Younis, A survey on clustering algorithms for wireless sensor networks. Computer communications, 2007. 30(14): p. 2826-2841.
5.J.N. Al-Karaki and A.E. Kamal, Routing techniques in wireless sensor networks: a survey. Wireless Communications, IEEE, 2004. 11(6): p. 6-28.
6.L. Subramanian and R.H. Katz. An architecture for building self-configurable systems. in Mobile and Ad Hoc Networking and Computing, 2000. MobiHOC. 2000 First Annual Workshop on. 2000: IEEE.
7.Z. Yong and Q. Pei," A energy-efficient clustering routing algorithm based on distance and residual energy for Wireless Sensor Networks. Procedia Engineering, 2012. 29: p. 1882-1888.
8.W.R. Heinzelman, A. Chandrakasan, and H. Balakrishnan. Energy-efficient communication protocol for wireless microsensor networks. in System Sciences, 2000. Proceedings of the 33rd Annual Hawaii International Conference on. 2000: IEEE.
9.A.M. Jasour, E. Atashpaz, and C. Lucas. Vehicle fuzzy controller design using imperialist competitive algorithm. in Second First Iranian Joint Congress on Fuzzy and Intelligent Systems, Tehran, Iran. 2008.
10.E. Atashpaz-Gargari and C. Lucas. Imperialist competitive algorithm: an algorithm for optimization inspired by
imperialistic competition. in Evolutionary Computation, 2007. CEC 2007. IEEE Congress on. 2007: IEEE.
11. S. Bayraklı, and S. Z.Erdogan. Genetic Algorithm Based Energ Efficient Clusters (GABEEC) in Wireless Sensor Networks, Procedia Computer Science 10, 247-254. 2012.
12.N.Enami, R .Askari Moghadam, K.Dadashtabar, M.Hoseini. Neural Network Based Energy Efficiency in Wireless Sensor Networks: a Survey’, In: International Journal of Computer Science & Engineering Survey (IJCSES) , Vol.1, No.1, August 2010, pp.39-55.
13.L.Shahvandi ,M.Teshnehlab, and A.Haroonabadi. A Novel Clustering in Wireless Sensor Networks used by Imperialist Competitive Algorithm, 2011.
