پروتکل های مسیریابی در WSNها (شبکه های سنسوری بی سیم)-(3) - مسیریابی سلسله مراتبی

پروتکل های مبتنی بر ساختار شبکه

ساختار شبکه های اساسی می تواند نقش مهمی در عملیات پروتکل مسیر یابی در WSN را ایفا کند. در این بخش ما جزئیات بسیاری از پروتکل هایی را که در این دسته قرار می گیرند، بررسی می کنیم.
پروتکل های مسیریابی بر اساس ساختار شبکه در زیر به سه دسته تقسیم شده :

1. مسیریابی مسطح یا یکدست(flat-based)
2. مسیریابی سلسله مراتبی (hierarchical-based)
3. مسیریابی مکانی(location-based)

مسیریابی سلسله مراتبی

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

پروتکل LEACH(Low Energy Adaptive Clustering Hierarchy) :

یک الگوریتم خوشه بندی سلسله مراتبی برای شبکه های سنسوری معرفی شده که آنرا LEACH (خوشه بندی سلسله مراتبی تطبیقی با انرژی کم) نامیدند. LEACH یک پروتکل براساس خوشه بندی است که شامل شکل گیری خوشه ی توزیع شده است. LEACH به طور تصادفی تعدادی از گره های سنسوری را به عنوان CH (سرخوشه یا cluster head) انتخاب می کند و نقش سرخوشه را بین گره ها می چرخاند تا مصرف انرژی بین سنسورهای شبکه به صورت متعادل توزیع شود. در LEACH گره های CH داده هایی که از گره ها یی که متعلق به خوشه ی مربوطه است رسیده اند، را فشرده می سازند و یک بسته ی جمع آوری(خوشه بندی) شده را (به منظور کاهش میزان اطلاعاتی که باید به BS متنقل شود) به B ارسال می کنند. LEACH از یک MAC از نوع TDMA/CDMA برای کاهش برخورد های درون خوشه ای و بین خوشه ای استفاده می کند. با این جود، جمع آوری(خوشه بندی) داده به طور متناوب خوشه بندی و متمرکز می شود. بنابراین، زمانیکه به نظارت مستمر توسط شبکه ی سنسوری نیاز باشد این پروتکل مناسبترین است. کاربرممکن نیست به همه ی داده ها فورا نیاز داشته باشد. از اینرو، انتقال داده ها به طور متناوب غیرضروری است، و ممکن است انرژی محدودی از گره های سنسوری تخلیه شود. بعد از یک دوره ی معین از زمان، چرخش تصادفی نقش CH اجرا می شود به طوریکه موجب اتلاف انرژی یکنواخت در سنسور های شبکه می شود. نویسندگان دریافتند، براساس مدل شبیه سازی آنها، که تنها 5 درصد از گره ها لازم است به عنوان CH ها عمل کنند.
عملیات LEACH به دو فاز مجزا به نام فاز راه اندازی و حالت پایدار تقسیم شده است. در فاز راه اندازی، خوشه ها انتخاب می شوند و CH ها انتخاب می شوند. در فاز حالت پایدار، انتقال داده ها واقعی به BS اتفاق می افتد. به منظور حداقل رساندن سربار، طول مدت فاز حالت پایدار طولانی تر از مدت زمان فاز راه اندازی است. در طول فاز راه اندازی، کسری از قبل تعیین شده از گره ها، p ، درصد پیشنهادی برای تعداد CH ها می باشد. یک گره سنسوری یک عدد را به صورت تصادفی بین 0 و 1 به عنوان r انتخاب می کند. اگر این عدد تصادفی کمتر از مقدار آستانه باشد، T(n) ، آن گره در دور فعلی CH می شود. مقدار آستانه براساس یک معادله که درصد مطلوب برای تبدیل شدن به یک CH در دور فعلی را ایجاد می کند، محاسبه می شود و مجموعه ای از گره ها که به عنوان CH در آخرین 1/P گذشته انتخاب نشده اند، با G نشان داده شده اند. این موضوع توسط زیر نشان داده می شود:
G مجموعه ای گره ها است که در انتخاب CH درگیر است. هر گره ي كه خود را در دور حاضر به عنوان CH انتخاب كرده است، يك پيغام همه پخشي به سا ير گره ها ارسال می کند. هر گره غیر CH، خوشه اي را كه به آن تعلق خواهد داشت را از روي قدرت سيگنال دريافتي محاسبه مي كند و در شرايط مساوي يك گره را به صورت تصادفي از بين خوشه ها انتخاب مي كند. بعد از دریافت همه ی پیام ها از گره هایی که به دسته آنها تعلق دارد. براساس تعداد گره های موجود در خوشه ، گره ی CH یک برنامه زمانی TDMA را تشکیل می دهد که به هر گره زمان ارسال اطلاعات آن را اعلان می کند. این برنامه زمانی به صورت همه پخشی(broadcast) به گره های موجود در دسته منعکس می شود.
در طول فاز حالت ثابت، گره های سنسوری می توانند سنس کنند و داده ها را به CH ها انتقال دهند. بعد از دریافت همه ی داده ها، و قبل از ارسال آنها به BS آنها را خوشه بندی می کند. بعد از یک زمان خاص، که به عنوان مقیاس تعیین شده، شبکه دوباره به فاز راه اندازی می رود و وارد دور دیگری از انتخاب CH جدید می شود. هر ارتباط خوشه از کدهای CDMA متفاوتی برای کاهش تداخل با گره های متعلق به خوشه های دیگر استفاده می کند.
اگرچه LEACH قادر به افزایش طول عمر شبکه است، اما هنوز هم تعدادی از مسائل در مورد مفروضات مورد استفاده در این پروتکل وجود دارد.در LEACH فرض می شود که همه ی گره ها در صورت نیاز می توانند با قدرت کافی برای رسیدن به BS منتقل کنند و اینکه هر گره دارای قدرت محاسباتی برای ساپورت از پروتکل های مختلف می باشد. بنابراین، در شبکه های مستقر در نواحی بزرگ اجرایی نیست. همچنین فرض می کند که گره ها همیشه برای ارسال داده دارند، و گره ها نزدیک به همدیگر قرار گرفته اند تا بدین صورت داده ها باهم همبستگی داشته باشند. این واضح نیست که چگونه تعداد CH های از پیش تعیین شده(p) به صورت یکنواخت در شبکه توزیع می شود. بنابراین، این امکان وجود دارد که CHهای انتخاب شده در یک بخش از شبکه متمرکز خواهد شد. از این رو ، برخی از گره ها هیچ CH ای در نزدیکی خودشان ندارند. علاوه براین، این ایده از خوشه بندی پویا موجب سربار اضافی می شود(تغییرات head و تبلیغات و غیره) که ممکن است بهره وری مصرف انرژی را کاهش می دهد. در نهایت، این پروتکل فرض می کند که همه ی گره ها در هر انتخاب دور، مقدار ظرفیت انرژی یکسانی داشته باشند. با این فرض که CH تقریبا همان مقدار انرژی برای هر گره مصرف می کند. این پروتکل باید برای محاسبه ی گره های انرژی غیریکنواخت توسعه یابد(به عنوان مثال استفاده از یک آستانه ی مبتنی بر انرژی). یک توسعه LEACH، LEACH با مذاکره، پیشنهاد شده است. موضوع اصلی این توسعه ی پیشنهاد شده مقدم کردن انتقال داده با مذاکره سطح بالا است که این عمل با استفاده از توصیف متادیتا که در پروتکل SPIN که قبلا بحث شده بود انجام می شود. این تضمین می کند که تنها داده ای که اطلاعات جدیدی را فراهم می کند به CHها منتقل می شود قبل از اینکه به BS منتقل شود. جدول1 SPIN را با LEACH و انتشار مستقیم بر اساس پارامتر های مختلف مقایسه می کند. این نکته از جدول برآمده که انتشار مستقیم یک رویکرد امیدوار کننده ای برای مسیریابی energy-efficient در WSN ها نشان می دهد(با توجه به استفاده پردازش های درون شبکه).

پروتکل PEGASIS(Power-Efficient Gathering in Sensor Information Systems)

یک بهبود برای پروتکل LEACH پیشنهاد شد. این پروتکل PEGASIS نام گرفت که بسیار شبیه پروتکل مبتنی بر زنجیره بهینه است. هدف اصلی این پروتکل این است که برای گسترش طول عمر شبکه، گره ها نیاز دارند فقط با نزدیک ترین همسایه هایشان ارتباط برقرار کنند و در ارتباط با ایستگاه اصلی(BS) گردش داشته باشند. وقتی یک دور ارتباط همه گره ها با ایستگاه اصلی به پایان رسید، دور جدید اغاز خواهد شد و همین طور الی اخر. این کاهش انرژی برای انتقال داده به ازای هر دور نیاز است به طوری که تخلیه انرژی به طور یکنواخت روی همه گره ها منتشر خواهد شد. بنابراین PEGASIS دو هدف اصلی دارد؛ اول، افزایش طول عمر هر گره با استفاده از تکنیک های شراکتی و در نتیجه طول عمر شبکه افزایش خواهد یافت. دوم، برای اینکه پهنای باند مصرف شده در ارتباطات کاسته شود، به گره هایی که به هم نزدیک هستند فقط اجازه هماهنگی محلی بین خودشان داده می شود. بر خلاف پروتکل LEACH، PEGASIS جلوی فرم خوشه را می گیرد و فقط از یک گره در یک زنجیره برای انتقال به ایستگاه اصلی بجای چندین گره استفاده می کند.
برای تعیین مکان نزدیک ترین گره همسایه در PEGASIS ، هر گره از شدت سیگنال برای اندازه گیری فاصله همه گره های همسایه استفاده می کند و سپس شدت سیگنال را طوری تنظیم می کند که فقط یک گره می تواند بشنود. زنجیره در PEGASIS شامل گره هایی است که به هم نزدیک ترین هستند و فرم یک مسیر به ایستگاه اصلی است. فرم متراکم داده به ایستگاه اصلی با هر گره در زنجیره ارسال می شود. ساخت زنجیره در یک سبک حریصانه انجام می شود. نتایج شبیه سازی نشان می دهد که PEGASIS توانایی افزایش طول عمر شبکه را دو برابر بیشتر از طول عمر شبکه تحت پروتکل LEACH دارد. این قبیل کسب کارایی از طریق کاهش سرباری که در LEACH به خاطر فرم خوشه پویا وجود دارد و کاهش تعداد انتقال ها و دریافت با استفاده از تراکم داده به دست می اید. اگرچه جلوی سربار حاصل از خوشه گرفته شد، اما PEGASIS هنوز نیاز به تنظیم توپولوژی پویا دارد. یک گره سنسور برای اینکه بداند داده هایش را کجا مسیردهی کند نیاز به اگاهی درباره وضعیت انرژی همسایه هایش دارد. این قبیل تنظیم توپولوژی می تواند سربار قابل توجهی به ویژه برای شبکه های مورد استفاده زیاد تولید کند. به علاوه PEGASIS فرض می کند که گره سنسور می تواند به طور مستقیم با ایستگاه اصلی ارتباط برقرار کند. در عمل گره های سنسور از ارتباط چند گام برای رسیدن به ایستگاه اصلی استفاده می کنند. بنابراین پروتکل PEGASIS فرض می کند که همه گره ها یک پایگاه داده کامل را درباره مکان همه گره ها در شبکه نگهداری می کنند. به علاوه، PEGASIS فرض می کند که همه گره های سنسور یک سطح انرژی دارند و مثل هم در یک زمان از کار خواهند افتاد. توجه داشته باشید که PEGASIS تاخیر زیادی را برای گره های دوردست در زنجیره تولید می کند. این پروتکل عقیده دارد یک لیدر تنها می تواند گلوگاه شود. در نهایت، اگرچه در بیشتر طرح ها، سنسورها ثابت یا بدون تحرک خواهند بود، اما در این پروتکل فرض شده بعضی از گره ها ممکن است متحرک باشند و برای همین روی عملکرد پروتکل تاثیر می گذارد.
نسخه گسترش یافته PEGASIS، مدل سلسه مراتبی ان است که با هدف کاهش تاخیر برای بسته ها در طول انتقال به ایستگاه اصلی تولید شده است. برای این منظور، انتقال همزمان داده ها به منظور اجنتاب از برخورد در این رویکرد که کدنویسی سیگنال و انتقال فضایی را ترکیب کرده، مورد مطالعه قرار گرفته است. در مورد اخیر، فقط گره های مجزای فضایی اجازه داده می شود تا در همان زمان انتقال دهند. پروتکل مبتنی بر زنجیره با گره های با قابلیت CDMA زنجیره ای از گره ها را می سازند که به شکل یک درخت سلسله مراتبی است، و هر گره ی انتخاب شده در یک سطح خاص، داده را به گره در سطح بالا از سلسله مراتب انتقال می هد. این روش تضمین می کند که انتقال داده به صورت موازی انجام می شود و تاخیر را به طور قابل توجهی کاهش می دهد. این نشان داده شده است که یک چنین توسعه ی سلسله مراتبی بهتر از طرح منظم PEGASIS عمل می کند(با یک فاکتور حدودا 60).

پروتکل TEEN و APTEEN (Threshold-Sensitive Energy Efficient Protocol)

دو پروتکل مسیریابی سلسه مراتبی TEEN (پروتکل شبکه سنسور موثر در انرژی حساس به استانه) و APTEEN (تناوب فعالانه TEEN) پیشنهاد شده اند. این دو پروتکل برای کاربردهای بحرانی از نظر زمان پیشنهاد شده اند. در TEEN گره های سنسور به صورت پیوسته حسگری می کنند، اما انتقال داده کمتر اتجام می شود. یک سنسور لیدر(CH) به بخش خودش یک سیگنال استانه قوی تر می فرستد، که مقدار استانه صفت حس شده است و یک استانه ضعیف، که یک تغییر کوچک در مقدار صفت حس شده است و گره را در حالت سوییچ روی انتقال دهنده و انتقال نگه می دارد . به این ترتیب استانه قوی سعی می کند تعداد انتقال ها را کاهش دهد؛ و یعنی گره ها مجازند تا وقتی که فقط صفت حس شده در محدوده Interest است انتقال داشته باشند. استانه ضعیف نیز تعداد انتقال ها را درصورتی کاهش می دهد که صفت حس شده تغییر کمتر داشته باشد یا بدون تغییر باشد. یک مقدار کوچک تر استانه ضعیف می تواند در هزینه افزایش مصرف انرژی تصویر دقیق تری بدهد؛ به این صورت که کاربر تعادل بین بهره وری انرژی و صحت داده را کنترل کند. وقتی لیدرها در حال تغییر هستند مقدار جدید برای پارامترهای بالا منتشر می شود. تصویر زیر بخش a :
اشکال اصلی طرح مذکور این است که اگر استانه ها دریافت نشوند، گره ها هرگز ارتباط برقرار نخواهند کرد و کاربر هیچ داده ای را از شبکه نخواهد گرفت.
گره ها محیط را به طور پیوسته حس می کنند. اولین بار یک پارامتر از مجموعه صفت با مقدار آستانه قوی می رسد، گره را در حالت سوییچ روی انتقال دهنده نگه می دارد و داده حس شده را می فرستد. مقدار حس شده در یک متغییر داخلی به نام SV(sensed value) ذخیره شده است. گره ها داده درون دوره خوشه جاری تنها زمانی که شرایط زیر برقرار باشد، منتقل می کند:
• مقدار فعلی صفت حس شده بزرگتر از آستانه ی قوی باشد.
• مقدار فعلی یا صفت حس شده با یک مقدار مساوی یا بزرگتر از آستانه ی ضعیف، با SV اختلاف داشته باشد.
عملکرد این پروتکل بدین صورت است که حسگرهایی که نزدیک هم هستند باهم یک خوشه تشکیل می دهند و این کار یک مرحله ي دیگر نیز ادامه پیدا می کند و در نهایت به ایستگاه پایه می رسد. چگونگی این کار در شکل زیرنشان داده شده است:
ویژگی های مهم TEEN شامل مناسب بودن آن برای کاربرد های بحرانی از نظر زمان در حسگری می باشد. همچنین از آنجایی که انتقال پیام مصرف انرژی بیشتری نسبت به حسگری داده دارد، مصرف انرژی در این طرح کمتر از شبکه های proactive است. آستانه ی ضعیف می تواند متفاوت باشد. در هر زمان تغییر خوشه، پارامتر های تازه پخش می شوند، به طوریکه کاربر در صورت نیاز می تواند تغییر دهد.
APTEEN یک پروتکل ترکیبی است که تناوب یا مقادیر استانه استفاده شده در پروتکل TEEN را بر طبق نیازهای کاربر و نوع کاربردها تغییر می دهد. در APTEEN ، لیدرها پارامترهای زیر را منتشر می کنند. (شکل بالا بخش b)
صفت ها: مجموعه ای از پارامترهای فیزیکی است که کاربر علاقه مند است اطلاعاتی را درباره ان به دست اورد.
استانه ها: این پارامتر شامل استانه قوی و استانه ضعیف است.
زمانبندی: شامل یک زمانبندی TDMA است که به هر گره یک برش زمانی اختصاص میدهد.
شمارش زمان : ماکزیمم دوره زمانی بین دو گزارش متوالی ارسال شده توسط یک گره است.
گره محیط را به صورت پیوسته حس می کند و فقط ان گره هایی که مقدار داده را در استانه شدید یا فراتر از ان حس کرده اند منتقل می کنند. برای یک بار که یک گره یک مقدار ار فراتر از استانه قوی حس می کند، ان داده را فقط وقتی منتقل می کند که مقدار ان صفت با یک مقدار بزرگ تر یا مساوی استانه ضعیف تغییر می کند.اگر یک گره داده را برای یک دوره زمانی برابر با شمارش زمان ارسال نکند، مجبور است حس کند و دوباره داده را منتقل کند. یک زمانبندی TDMA استفاده شده و هر گره خوشه، یک برش زمانی برای انتقال داده می گیرد. از این رو APTEEN از زمانبند TDMA تغییر یافته برای پیاده سازی شبکه ترکیبی استفاده می کند. ویژگی های اصلی این پروتکل سیاست ترکیب Reactive و Proactive است. این پروتکل با اجازه دادن به کاربر برای تنظیم فاصله ی CT انعطاف پذیری را بالا می برد، و مقدار آستانه برای مصرف انرژی با تغییر CT می تواند کنترل شود. اشکال اصلی این طرح پیچیدگی اضافی مورد نیاز برای پیاده سازی توابع آستانه و CT است. شبیه سازی TEEN و APTEEN نشان داده است که این دو پروتکل بهتر از LEACH است. آزمایش ها نشان می دهند که کارایی APTEEN ها در اتلاف انرژی و طول عمر شبکه چیزی بین LEACH و TEENاست. TEEN با کاهش تعداد انتقالات بهترین کارایی را ارائه می دهد. اشکال اصلی این دو روش سربار و پیچیدگی مربوط به شکل گیری خوشه ها در چندین سطح، روش های پیاده سازی توابع مبتنی بر استانه و رسیدگی به نحوه نامگذاری مبتنی بر صفت و پرس و جوها است .

شبکه ارتباطی با حداقل انرژی(MECN) کوچک:

پروتکلی ارائه شده که انرژی موثر زیر شبکه را محاسبه می کند، MECN برای یک شبکه ی خاص سنسوری با GPS های با توان پایین بکارمی رود. MECN یک ناحیه ی تقویت را برای هر گره تعیین می کند. ناحیه ی تقویت شامل گره هایی در منطقه ی اطراف آن است که انتقال از طریق این گره ها بهره وری انرژی آن را نسبت به روش انتقال مستقیم بیشتر می کند. محوطه ی گره ی i با اجتماع همه ی ناحیه های تقویت که می تواند به گره ی i برسد، ایجاد می شود. ایده ی اصلی mecn پیداکردن زیرشبکه ای است که گره های کمتری خواهد داشت و نیاز به انرژی کمتری برای انتقال بین هر دو گره ی خاص دارد. در این روش، مسیرهای حداقل انرژی کلی بدون درنظرگرفتن همه ی گره های شبکه پیدا می شود. این روش با استفاده از یک جستجوی محلی برای هر گره با توجه به ناحیه ی تقویت آن، انجام می شود. mecn خودش تغییر شکل می دهد و بدین گونه که به صورت پویا گره ی معیوب را درست می کند یا یک سنسور جدید را بکار می گیرد. mecn کوچک(SMECN) یک MECN توسعه یافته است. در MECN، فرض بر این است که هر گره می تواند به هر گره ی دیگر منتقل شود، که در هر زمان امکان پذیر نیست. در SMECN موانع ممکن بین هر جفت از گره ها درنظرگرفته می شود. با این حال، در این مورد از MECN ، هنوز فرض شده که شبکه به طور کاملا متصل باشد. زیرشبکه های ساخته شده توسط SMECN برای حداقل تقویت انرژی به طور قابل اثبات کوچکتر(از نظر تعداد لبه یا یال) از اونی که در mecn ساخته شده، می باشد. از اینرو، اگر ناحیه ی پخش به صورت دایره ای شکل اطراف گره ی پخش کننده(برای تنظیم انرژی معین) باشد، زیرشبکه ساخته شده توسط SMECN(به عنوان مثال،گراف G) کوچکتر از اونی که توسط MECN ساخته شده، می باشد. زیر گراف G از گراف G، که نشانگر شبکه ی سنسوری است، به خاطر شرایط زیر استفاده از انرژی را به حداقل می رساند:
• تعداد لبه ها(یالها) در گراف G کمتر از G است در حالی که شامل تمام گره های G می باشد.
• انرژی مورد نیاز برای انتقال داده از یک گره به تمام همسایگان خود در گراف G کمتر از انرژی مورد نیاز برای انتقال به تمام همسایگانش در گراف G است.فرض کنید که r = (u, u1,…, v) یک مسیر بین U و V است که K-1 گره میانی u1, … uk–1 در بر می گیرد. کل مصرف انرژی یک مسیر مانند r برابر است با:

که u = u0 و v = uk است، وانرژی مورد نیاز برای انتقال داده تحت این پروتکل برابر است با
برای برخی ازمقادیر ثابت t ، n توان اتلاف مسیر از مدل انتشار رادیویی در فضای باز است(n 2)، و d(u,v) فاصله ی بین u و v است. فرض بر این است که یک دریافت در گیرنده مقدار ثابتی از انرژی (که با c نشان داده شده را) می گیرد. زیرشبکه ی محاسبه شده توسط SMECN در ارسال پیام در مسیرهای با حداقل انرژی کمک می کند. به هر حال، در این مفهوم الگوریتم پیشنهادی محلی(local) است که در واقع مسیر حداقل انرژی را پیدا نمی کند، اما فقط زیر شبکه ای ایجاد می کند که وجود این مسیر را تضمین می کند. علاوه بر این، زیر شبکه ی ساخته شده توسط SMECN این احتمال را بیشتر می کند که مسیر استفاده اونی است که نیاز به مصرف انرژی کمتری دارد. همچنین، پیداکردن یک زیرشبکه با تعداد یالهای کمتر در الگوریتم موجب سربار بیشتری می شود.

پروتکل SOP(self-organizing protocol)

یک پروتکل SOP (خود سازماندهی) و یک طبقه بندی کاربردی که برای ایجاد معماری برای حمایت از سنسورهای ناهمگن استفاده می شود، توصیف شده است. علاوه براین، این سنسورها می توانند متحرک یا ساکن باشند. بعضی از سنسورها پس از بررسی محیط، داده را به یک مجموعه معین شده از گره ها ارسال می کنند که مثل مسیریابها(یا لیدرها) عمل می نمایند. گره های مسیریاب ساکن هستند و ستون فقرات یا زیرساختی برای ارتباطات می باشند. داده جمع اوری(خوشه بندی) شده از طریق مسیریابها به ایستگاه اصلی قوی تری ارسال می شود. هر گره حس کننده برای اینکه بخشی از شبکه باشد باید بتواند به یک مسیریاب دسترسی داشته باشد. در این پروتکل یک معماری مسیریابی که به ادرس دهی هر گره سنسور نیاز دارد، پیشنهاد شده است. گره های حس کننده از طریق ادرس یک گره مسیریاب که به ان متصل شده اند قابل شناسایی هستند. معماری مسیریابی سلسله مراتبی است که گروهی از گره ها در صورت نیاز مرتب و ادغام شده اند. الگوریتم حلقه های محلی مارکوف(LML)، که گام های تصادفی روی درخت پوشای یک گراف برمی دارد، برای پشتیبانی تحمل خطا و همچنین به عنوان ابزاری برای پخش(broadcast) مورد استفاده قرار گرفت. چنین رویکردی که مشابه ایده یک شبکه مجازی است، در بعضی از پروتکل های دیگر که بعدا تحت عنوان پروتکل های مسیریابی مبتنی بر مکان بحث می شود، استفاده می شود. در این روش، سنسور می توانند اساسا در معماری مسیریابی ادرس داده شوند. از این رو معماری مسیریابی مناسب کاربردهایی است که ارتباط به یک گره ویژه نیاز است. به علاوه این الگوریتم هزینه کمی برای نگهداری جدول مسیریابی و نگهداری یک مسیریابی سلسله مراتب متعادل دارد. همچنین انرژی مصرف شده برای یک پیام، کمتر از پروتکل SPIN است. این پروتکل با این حال، یک پروتکل بنابه درخواست(عندالمطالبه) نیست، به خصوص در فاز سازماندهی الگوریتم و سربار اضافی تولید می کند. موضوع دیگر نیز در مورد ساخت سلسله مراتب زمانی اتفاق می افتد که تعداد زیادی حفره در شبکه وجود داشته باشد و از این رو احتمال اعمال دوباره فاز سازماندهی افزایش می یابد که یک عمل پرهزینه خواهد بود.

مسیریابی خوشه های سنسور (Sensor aggregates routing:)

الگوریتمی برای ساخت و نگهداری خوشه های سنسور پیشنهاد شده است که هدف از ان نظارت در یک محیط مشخص (کاربردهای ردیابی هدف) است. خوشه ان دسته از گره هایی در شبکه است که یک گروه بندی را برای شرکت در کار پردازش ارائه می کند. پارامترهای این خوشه بستگی به کار و نیازمندی های منبع دارد. تشکیل خوشه های مناسب سنسور از نظر تخصیص منابع برای حسگری و وظایف ارتباطات مورد بحث قرار گرفت. سنسورها در فیلد سنسور بر اساس شدت سیگنالشان به خوشه ها تقسیم شده اند، به طوری که به ازای هر خوشه فقط یک نقطه اوج وجود دارد. سپس لیدرهای خوشه محلی انتخاب شده اند. یک نقطه اوج ممکن است یک هدف را نشان دهد و همچنین در حالتی که نقطه اوج توسط نویز منابع تولید می شود، هدفی را نشان ندهد. برای انتخاب لیدر، بین سنسورهای همسایه تبادل اطلاعات نیاز است. اگر یک سنسور بعد از تبادل بسته-ها با همه همسایه های یک گام خودش، متوجه شود که از همه همسایه های یک گام خودش در ناحیه سیگنال بالاتر است، خودش را به عنوان یک لیدر اعلام می کند. این الگوریتم مسیریابی مبتنی بر لیدر فرض می کند سرخوشه منحصر به فرد، ناحیه جغرافیایی همکاری را می داند.
برای این پروتکل سه الگوریتم پیشنهاد شده است. در اولین روش مدیریت تراکم توزیع شده DMA است که برای شکل دهی خوشه های الگوریتم و نظارت بر هدف است. پروتکل شامل یک گزاره تصمیمP برای تصمیم گیری هر گره است اگر این گره در خوشه بندی مشارکت کند و یک طرح تبادل پیام M در مورد چگونگی گروهبندی گزاره برای هر گره بکار برده شد. یک گره اگر متعلق به یک خوشه باشد، بر اساس نتیجه ی اعمال گزاره به داده ی گره و بعلاوه اطلاعات گره های دیگر تصمیم گیری می کند. در نهایت زمانیکه فرایندها به هم جمع می شوند(همگرا) خوشه ها تشکیل می شوند. دومین الگوریتم نظارت فعال مبتی بر انرژی(EBAM) است که سطح انرژی در هرگره را با محاسبه ناحیه برخورد سیگنال، ترکیب شکل وزنی انرژی هدف شناسایی شده در هر سنسور تحت اثر، با فرض اینکه هر سنسور هدف سطح انرژی ثابت یا برابر دارد. سومین الگوریتم EMLAM اتلاف انرژی ثابت یا مساوی هدف را حذف نموده و از نتیجه ارزیابی برای پیش بینی امکان نحوه ترکیب سیگنال های اهداف در هر سنسور استفاده می کند. این فرایند تکرار می شود تا ارزیابی به قدر کافی مطلوب شود. طرح مدیریت شروع ردیابی توزیع شده، با الگوریتم ردیابی مبتنی بر لیدر توصیف شده و یک سیستم مقیاس پذیر را شکل میدهد. سیستم در ردیابی چندین هدف وقتی به خوبی کار می کند که اهداف مزاحم نیستند و این سیستم می تواند از تداخل بین اهدف زمانیکه اهداف جدا از هم حرکت می کنند بهبود یابد.

مسیریابی با معماری شبکه ی مجازی(VGA):

یک الگوی مسیریابی موثر در انرژی پیشنهاد شده که برای تراکم داده و پردازش درون شبکهای برای بیشینه کردن طول عمر شبکه به کار می رود . برای گره ثابت و خیلی کم تحرک در بسیاری از کاربردها در شبکه های سنسور بیسیم یک روش متعارف، مرتب کردن گره ها در یک توپولوژی ثابت است. یک روش-free GPS برای ساخت خوشه ها که ثابت، مساوی و مجاور هستند و هم پوشانی ندارند با اشکال منظم استفاده شده است. همچنین درخوشه های مربع برای به دست اوردن یک توپولوژی مجازی مستقیم الخط استفاده شده است. در داخل هر ناحیه، یک گره به صورت بهینه به عنوان لیدر(CH) انتخاب می شود. تراکم داده در دو سطح محلی و سپس سراسری انجام می شود. مجموعه ای از لیدرها به عنوان متراکم کننده های محلی(LA) مطرح هستند و تراکم محلی را انجام می دهند، در حالی که یک زیر مجموعه از این متراکم کننده های محلی برای انجام تراکم سراسری استفاده می شوند. با این وجود، انتخاب بهینه از نقاط تراکم سراسری، MA(متراکم کننده اصلی) نام گرفت که از مسائل NP-hard است. تصویر زیر نمونه ای از منطقه بندی ثابت را نشان می دهد و در نتیجه معماری شبکه های مجازی (VGA) برای انجام دو سطح جمع آوری داده ها استفاده شده است.
توجه داشته باشید که محل BS لزوما در دورترین نقطه ی شبکه نیست. بلکه می توان آن(BS) را در هر نقطه قرار داد. دو راه-حل برای مسیریابی با مسئله تراکم داده ارائه شده است: یک الگوریتم دقیق با استفاده از یک فرمولاسیون برنامه خطی صحیح(ILP)، و برخی از الگوریتم های نزدیک به بهینه اما ساده و تقریبا کارا : یک الگوریتم ژنتیک بر مبنای هیوریستیک، یک k-means هیوریستیک، و یک هیوریستیک حریصانه. ، همچنین یکی دیگر از روش های هیوریستیک کارا، هیوریستیک مبتنی بر تجمع خوشه(CBAH)، برای به حداقل رساندن مصرف انرژی در شبکه پیشنهاد شد و از اینرو طول عمر شبکه را افزایش داد. هدف الگوریتم ها انتخاب تعدادی گره سنسور متراکم کننده اصلی(MA) خارج از سنسورهای متراکم کننده محلی(LA) برای بیشینه کردن طول عمر شبکه است. برای یک سناریوی واقعی، فرض شده که وجود گره هایLA، در گروه های که هم پوشانی دارند امکان پذیر است. اعضای هر گروه یک پدیده را حس می کنند و تعابیر خواندن انها قرینه است، اما هر گرهLA کهدر ناحیه هم پوشانی موجود است داده را به MA مختص خود برای هر گروه که متعلق به ان است می فرستد. این مطلب مشکل اختصاص MAها به LAها در CBAH شبیه به مسئله ی بسته بندی مخزن(bin) کلاسیک است، تفاوت عمده این است که نه هویت و نه مقدار انرژی هر MA که برای LAهای مختلف استفاده خواهد شد، شناخته شده نیست. در CBAH ، مجموعه ای از MAها بر اساس پرشدن تدریجی برخی از مخازن دارای ظرفیت، انتخاب می شوند. علاوه بر سریع بودن و مقیاس پذیربودن به شبکه های سنسوری بزرگ، الگوریتم های تقریبی در نتایج نه چندان دور از راه حل مطلوب ارائه می کنند.

مسیریابی سلسله مراتبی آگاه از انرژی (HPAR)

این پروتکل شبکه را به گروه هایی از سنسورها تقسیم می کند. هر گروه از سنسورهای مجاور هم با هم به عنوان یک ناحیه خوشه شده اند و هر ناحیه به عنوان موجودیت مستقل عمل می کند. برای انجام مسیریابی هر ناحیه تصمیم گیری می کند که چگونه یک پیام سلسله مراتبی از میان ناحیه های دیگر مسیردهی شود به طوری که عمر باتری این گره ها در سیستم بیشترین باشد. پیام ها در طول مسیر مسیردهی می شوند که حداکثر از مجموع حداقل قدرت باقی مانده را دارد، که مسیر max-min نامیده شد. انگیزه این است که استفاده از گره های با قدرت باقیمانده ی بالا ممکن است گران تر از مسیر با حداقل مصرف انرژی باشد. یک الگوریتم تقریبی که الگوریتم max-min zPmin نامیده شده است. مسئله دشوار الگوریتم اساسا تعادل بین کم کردن مصرف انرژی و به حداکثر رساندن حداقل قدرت باقی مانده از شبکه است. از این رو الگوریتم سعی می کند تا به یک مسیر Max-Min با محدود کردن مصرف انرژی ان به صورت زیر کمک کند. اول، الگوریتم مسیر با حداقل مصرف انرژی (Pmin) را با استفاده از الگوریتم مسیریابی دایجکسترا پیدا می کند. دوم، الگوریتم مسیری را که منجربه مصرف انرژی کمتری می شود پیدا می کند. الگوریتم پیشنهاد شده سعی می کند تا معیارهای هر دو راه حل را بهینه کند. این مسئله با کم کردن حداقل مصرف انرژی برای این پیام تا برابر zPmin شود و با پارامتر z ³ 1 برای محدود کردن مصرف انرژی برای ارسال یک پیام به zPmin به انجام می رسد. این الگوریتم zPmin را تا حداکثر کردن حداقل انرژی باقیمانده مصرف می کند. الگوریتم دیگر که بر max-min zPmin تکیه کرده ، مسیریابی مبتنی بر ناحیه نامیده می شود. مسیریابی مبتنی بر ناحیه یک روش سلسله مراتبی است که ناحیه پوشیده شده توسط شبکه سنسور به تعدادی ناحیه کوچک تر تقسیم شده است. برای ارسال یک پیام از طریق محل ناحیه یک مسیر سراسری از یک ناحیه به ناحیه دیگر پیدا می شود. سنسورها در یک ناحیه به صورت خود گردان مسیریابی محلی را هدایت می کنند و در ارزیابی سطح انرژی ناحیه سهیم می شوند. هر پیام از طریق نواحی با استفاده از اطلاعات درباره براورد انرژی ناحیه مسیردهی می شود. یک کنترلر سراسری برای مسیریابی پیام در نقش مدیریت منابع اختصاص داده شده. این کنترلر ممکن است گره با بالاترین سطح انرژی باشد. اگر شبکه بتواند به تعداد نسبتا کمی از نواحی تقسیم شود، مقیاس برای الگوریتم سراسری کاهش می یابد. اطلاعات سراسری که برای ارسال هر پیام در سراسر شبکه مورد نیاز است، بوسیله ی برآورد سطح انرژی هر ناحیه خلاصه سازی شده است. اگر ناحیه فعلی بتواند به ناحیه همسایه بعدی در آن مسیر برود، یک گراف ناحیه برای نشان دادن رئوس ناحیه همسایه ای به هم متصل شده استفاده شده است. هر راس ناحیه دارای یک سطح انرژی از مجموع 1 می باشد. هر راس ناحیه با سطح انرژی تخمینی خودش ، توسط یک پروسیجر برچسب گذاری شده، که این الگوریتم بلمن فورد اصلاح شده است. بعلاوه، دو الگوریتم برای انتخاب مسیر محلی و سراسری طرح ریزی شده است که از گراف ناحیه استفاده می کند.

روش TTDD(انتشار اطلاعات دو ردیفه)

یک روش ارائه شده، TTDD است . این روش ارسال داده به چندین ایستگاه اصلی متحرک را فراهم می کند. در TTDD، هر منبع داده به صورت Proactive یک ساختار grid(شبکه توری) را می سازد که برای ارسال داده به Sinkهای متحرک با فرض اینکه گره های سنسور ثابت و اگاه از مکان هستند، استفاده شده است. در این پروتکل گره های سنسور ثابت و اگاه از مکان هستند، در حقیقت Sinkها ممکن است مکانشان را به صورت پویا تغییر دهند. وقتی یک رویداد اتفاق می افتد، سنسورهای اطراف ان، سیگنال را پردازش می کنند و یکی از انها برای تولید گزارش داده به منبع می آید. گره های سنسوری نیز از ماموریت خود اگاه هستند که اغلب تغییر نخواهند کرد. برای ایجاد ساختار Grid، یک منبع داده خودش را به عنوان نقطه شروع انتخاب می کند و یک پیام اعلان داده را به چهار نقطه مجاورش با استفاده از ارسال جغرافیایی حریصانه ساده می فرستد. هنگامیکه این پیام به گره ی نزدیک به نقطه ی تقاطع (مشخص شده در پیام) می رسد، متوقف خواهد شد. در طول این فرایند هر گره میانی اطلاعات منبع را ذخیره می کند و در ادامه پیام را به همسایه مجاورش به جز یکی که پیام از انجا می اید ارسال می کند. این فرایند تا زمانی که پیام در مرز(لبه) شبکه متوقف شود ادامه پیدا می کند. گره هایی که پیام منبع را ذخیره کرده اند به عنوان نقاط توزیع اطلاعات انتخاب می شوند. بعد از این فرایند، ساختار Gridبه دست می اید. با استفاده از Grid، یک ایستگاه اصلی می تواند یک پرس و جو را ارسال کند که به نزدیک ترین نقطه در سلول محلی برای دریافت داده ارسال خواهد شد. سپس پرس و جو از طریق نقاط توزیع اطلاعات دیگر به صورت جریان به منبع ارسال می شود. در ادامه داده تقاضا شده در مسیر عکس به سمت Sinkارسال می شود. مسیر ارسال به عنوان تغییر مکان BS در فیلد سنسور بکار گرفته شد. اگرچه TTDDیک روش مسیریابی کارامد است، یک سری مسائل مربوط به اینکه الگوریتم چگونه مکان اطلاعات را به دست می اورند، وجود دارد که برای تنظیم و راه اندازی ساختار Gridنیاز است. طول مسیر ارسال در TTDDنسبت به طول کوتاه ترین مسیر بیشتر است. نویسندگان TTDD معتقدند که بهینگی کمتر در طول مسیر در تقویت مقیاس پذیری با ارزش است. سرانجام، نحوه کار TTDD هنوز یک سوال قابل بحث است. مقایسه نتایج بین TTDDو انتشار مستقیم نشان می دهد کهTTDDمی تواند طول عمر بیشتر و تاخیرهای ارسال داده کوتاهتر را به دست اورد، اما سربار حاصل از نگهداری و محاسبه دوباره شبکه به عنوان تغییرات توپولوژی شبکه ممکن است بالا باشد. گذشته از این، در TTDD فرض شده که یک سیستم موقعیت یاب بسیار دقیق در دسترس است، که هنوز برای شبکه های سنسور بیسیم در دسترس نیست.
در بالا، پروتکل های تخت و سلسله مراتبی نشان داده شده که در بسیاری از جنبه ها باهم متفاوت اند. در اینجا روش های مسیریابی مختلف برای شبکه های سنسوری تخت و سلسله مراتبی که در جدول2 نشان داده شده با هم مقایسه می شوند.
جدول زیر مقایسه مسیریابی سلسله مراتبی و تخت می باشد:
*** منبع مقاله :
متن منابع