عوامل موثر در طراحی پروتکل های مسیر یابی برای طراحی الگوریتم های موثر مسیریابی، باید به چندین عامل موثر در طراحی دقت نمود که در زیر بیان می شود: پویایی شبکه . سه عنصر مهم در شبکه های سنسوری ، نودجمع آوری کننده ، نودهای سنسوری و اتفاق های مورد بررسی می باشند که به صورت ثابت و یا متحرکند . مسیریابی نودهای متحرک (چه نود جمع آوری و یا چه نودهای سنسوری)کار پیچیده تری می باشد. به همین ترتیب دنبال کردن اتفاقات پویا نیز دشوارتر خواهد بود.
عوامل موثر در طراحی پروتکل های مسیر یابی برای طراحی الگوریتم های موثر مسیریابی، باید به چندین عامل موثر در طراحی دقت نمود که در زیر بیان می شود: پویایی شبکه . سه عنصر مهم در شبکه های سنسوری ، نودجمع آوری کننده ، نودهای سنسوری و اتفاق های مورد بررسی می باشند که به صورت ثابت و یا متحرکند . مسیریابی نودهای متحرک (چه نود جمع آوری و یا چه نودهای سنسوری)کار پیچیده تری می باشد. به همین ترتیب دنبال کردن اتفاقات پویا نیز دشوارتر خواهد بود. چیدمان نود. چیدمان نود ها می تواند از پیش تعیین شده یا اتفاقی باشد. چیدمان معین نودها، براساس طرحی از پیش تعیین شده می باشد و داده از مسیرهای از پیش تعیین شده می تواند مسیر یابی شود. در صورتیکه ، به کارگیری اتفاقی نودها چندین مسئله از جمله پوشش، کلاسترینگ بهینه و موارد دیگر را پیش می آورد که باید بررسی شوند. شبکه چند پرشه و یا یک پرشه . از آنجا که انرژی ارسالی با مجذور فاصله در ارتباط مستقیم است ، شبکه های چند پرشه برای صرفه جویی در انرژی مناسب ترند. اما شبکه های چند پرشه مسائلی چون ، مدیریت توپولوژی ،و کنترل دسترسی به مدیا را نیز به همراه می آورند. مدل های گزارش داده . در شبکه های سنسوری ، مدل های گزارش می تواند به صورت ممتد، براساس پرسش ، و یا بر اساس یک اتفاق باشد.مدل های گزارش طراحی شبکه را تحت تاثیر قرار می دهند. مثلا مدل ممتد مقدار زیادی داده تولید می کند و بنابراین مسیریابی باید به جمع آوری داده نیز دقت داشته باشد. تنوع نودها . بعضی کاربردها ، ممکن است نیاز به ترکیب نودهای سنسوری با انواع دیگر نود با قابلیت های متفاوت را داشته باشند. داده ی تولیدی از چندین سنسور متفاوت می تواند منجر به تولید داده با نرخ های متفاوت ، مدل های متفاوت گزارشی و محدودیت های مختلف کیفیت سرویسی ، شود. چنین محیط ناهمگنی نیاز به مسیریابی پیچیده تری دارد. جمع آوری داده . جمع آوری داده ترکیب داده های حاصل از چندین منبع مختلف بر اساس تابع جمع آوری کننده ی خاصی چون : حذف تکراری ها، کمینه گیری ،بیشینه گیری و یا حداقل سازی می باشد.این روش برای کاهش داده ی تولیدی از چندین منبع و صرفه جویی در انرژی صورت می گیرد. اما این روش به افزایش پیچیدگی کمک کرده و استفاده از روش های امنیتی را تقریبا غیر ممکن می سازد. ویژگی های مطلوب در مسیریابی از ویژگی های مطلوب مسیریابی می توان به موارد زیر اشاره کرد: عملیات توزیعی : پروتکل قطعا باید توزیعی باشد و نباید بر نود مرکزی وابسته باشد که در شبکه های ایستا مشاهده می شود. تفاوت در اینجاست که در شبکه های موردی نودها به راحتی به سیستم وارد و یا از آن خارج می شوند و به دلیل تحرک ، شبکه می تواند تکه تکه شود. بدون حلقه بودن : برای افزایش کارایی نیاز به مسیریابی هایی داریم که تضمین کند مسیر بدون حلقه است تا از اتلاف پهنای باند جلوگیری شود. عملیات مبتنی بر تقاضا: برای کاهش سربار کنترلی در شبکه و نیز جلوگیری از اتلاف منابع شبکه ، پروتکل باید واکنشی باشد. یعنی فقط در هنگام نیاز اطلاعات کنترلی ، پخش شود. حمایت از پیوندهای یک طرفه : در محیط رادیویی ممکن است ، پیوندهای یک طرفه بوجود آید. استفاده از این پیوندها ، باعث بهبود کارایی پروتکل می شود. امنیت : محیط رادیویی بیشتر در معرض خطر حمله تظاهر[17]، می باشد. پس باید مسیریابی بگونه ای باشد که مطمئن باشیم که پروتکل رفتار مطلوب ما را ارائه می دهد. تشخیص هویت و رمز نگاری ، به همراه کلید های توزیعی در دست نودها،به نظر راهی برای این امر می باشد. استفاده از IP-sec* با استفاده از روش تونل زنی برای ارسال بسته ها نیز مورد بحث می باشد. نگهداری انرژی : نودها در شبکه می تواند رایانه ی همراه و یا PDA و یا سنسور با انرژی محدود باشند. پس مسیر یابی با توجه به این نکته امری مهم می باشد. چند مسیری : برای کاهش واکنشی به تغییرات توپولوژیکی و نیز ازدحام در شبکه ، نیاز به چند مسیری داریم. اگر مسیری غیرمعتبر شود ممکن است امکان استفاده از مسیر دیگر همچنان مهیا باشد و از ایجاد مسیر دیگر و سربار عملیات کشف مسیر جلوگیری می کند. پشتیبانی از کیفیت سرویس : پشتیبانی از نیاز های کیفیت سرویس امری بسیار مطلوب می باشد که برای کاربردهایی چون realtime مورد استفاده قرار می گیرد. جلوه های متفاوت ارسال به جلو در این قسمت مسیر یابی را از دید دیگری بررسی می کنیم. مسیریابی تک پخشی ، همه پخشی و انواع آن را بیان خواهیم کرد. روش های ارسال به جلو و انواع آن هرگاه که نود منبعی نتواند داده را مستقیما به مقصد برساند و مجبور به اتکا به نودهای میانی باشد شبکه ی چند پرشی [18] ،ایجاد شده است مانند شکل 1-3. در چنین شبکه ای نود میانی باید تصمیم بگیرد که به کدام همسایه، بسته ی آمده را ارسال کند. این عمل ارسال به جلو[19] نامیده می شود. شکل 1-3. نمونه ای از مسیریابی چند پرشه- نود S بسته به نود D ارسال می کند. ساده ترین ارسال به جلو عمل flooding می باشد. ارسال به تمام همسایگان انجام میگیرد و مطمئنا داده به مقصد میرسد. برای گردش بیش از حد آن ، نودها فقط باید بسته هایی که تاکنون ندیده اند را ارسال به جلو کنند. همچنین از زمان انقضا (همچون حداکثر تعداد پرش ها)نیز برای بسته ها معمولا استفاده می شود. روش دیگر ارسال بسته نه به تمامی همسایه ها، بلکه به تعداد دلخواهی می باشد. در این روش شیوعی[20] ، بسته به طور اتفاقی در شبکه به امید پیدا کردن مقصد در حرکت خواهند بود. این روش ، تاخیر می تواند خیلی زیاد شود. این دو روش نهایت های گستره مسیریابی هستند. روش های میانه ای نیز وجود دارد. مثلا منبع می تواند بیش از یک بسته را به پیمایش اتفاقی در شبکه ، بفرستد و یا بسته ی ورودی به زیر مجموعه ای از همسایه ها فرستاده شود که بر اساس الگوریتم های کنترل توپولوژیکی می تواند مشخص شود. این روش گاهی روش سیل آسای کنترل شده[21] نیز نامیده می شود. گرچه این روش ها ساده هستند اما کارایی آنها از لحاظ تعداد بسته های ارسالی یا تاخیر بسیار ضعیف هستند.این ضعف ها به دلیل در نظر نگرفتن توپولوژی شبکه می باشد. مثلا در شکل 1-3 ، نود S بسته را حتی به نود A که دورتر از خود منبع نیز می باشد، ارسال می کند. بنابراین اطلاعاتی درباره مناسب بودن همسایه ها در فرایند ارسال ،باید در نظر گرفته شود. مناسبی یک همسایه با هزینه[22] ای که نود برای ارسال بسته به مقصد بوسیله آن همسایه ی خاص، مواجه است بدست می آید. این هزینه در معیار های مختلف مانند کمترین تعداد پرش یا حداقل انرژی مورد نیاز برای رسیدن به مقصد ، محاسبه می شود. این اطلاعات در جداول مسیریابی نگه داشته می شوند که نمونه ای از آن را در شکل 1-4 می بینید. شکل1-4.جدول مسیر یابی برای نود S شکل 1.3 با معیار تعداد پرش محاسبه ی این جداول مسیر یابی به کمک الگوریتم های مسیریابی به کمک پروتکل مسیر یابی انجام می گیرد. در شبکه های سیمی ،پروتکل ها معمولا وضعیت شبکه یا الگوریتم ها ی بردار فاصله ای (چون دیکسترا یا Bellman-Ford) می باشند. در شبکه های بی سیم واحتمالا متحرک روش های دیگری مورد استفاده قرار می گیرد. از ویژگی های این پروتکل های مسیریابی ، سربار کم ، توزیعی و خود سازمان دهی می باشد که بتوانند با توپولوژی متغیر شبکه خود را وفق دهند. این روش مسیریابی موردی مورد توجه زیاد محققین قرار گرفته است. در یک رده بندی * این پروتکل ها به دودسته ی تقسیم می شوند. پروتکل های مبتنی بر جدول [23] یا پیش فعالی[24] که به نوعی "سنت گرا[25]" می باشد زیرا سعی در نگه داری اطلاعات دقیق در هر جدولش دارد(مانند پروتکل DSDV). پروتکل های مبتنی بر تقاضا[26] که سعی در نگه داری اطلاعات مسیریابی در تمامی زمان ها ندارد. بلکه فقط وقتی که بسته ای برای ارسال دارد و اطلاعاتی از مسیر به سمت مقصد از پیش ندارد، جداول مسیر یابی را می سازد. (مانند پروتکل AODV) توجه شود که مرز این دو خیلی جدا از هم نیست و راه های ترکیبی نیز در این بین وجود دارد.مروری بر این مباحث و پروتکل های مربوط در انواع کتاب های شبکه های موردی یافت می شود و مقالات مرورگر یافت می شود. مشکل مشترک بسیاری از این پروتکل ها نیاز به استفاده از پیام های کنترلی سیل آسا برای تشخیص توپولوژی شبکه و پیدا کردن مقصد می باشد. گستره ی شبکه های موردی بسیار گسترده است و تمام آنها مناسب شبکه های سنسوری نمی باشد(ماند مسیریابی ترافیک چند رسانه ای ). علاوه بر مسیر یابی تک ارسالی[27] که یک نود بسته را به نود مشخص دیگری ارسال می کند ، همه پخشی[28] (ارسال به تمامی نودها در شبکه) و چند پخشی[29](ارسال به گروهی از نودها) نیز از وظایف مهم در WSN می باشد. یک راه تعریف گروه مشخص کردن ناحیه جغرافیایی است که تمامی آن نودها باید دریافت انجام دهند. مسیر یابی تک پخشی انرژی-موثر در نگاه اول ، مسیریابی تک پخشی انرژی-موثر مسئله ای ساده می نماید: گراف شبکه را گرفته و به هر پیوند هزینه ای که مصرف انرژی در آن پیوند را منعکس کند، اختصاص دهید. سپس مسیری با کمترین هزینه را در گراف انتخاب کنید. در واقع روش های متعددی برای موثر بودن مصرف انرژی می توان در نظر گرفت*. کمینه کردن انرژی برای هر بسته (یا هر بیت) . ساده ترین روش ، نگاه کردن به مصرف انرژی برای انتقال بسته در چندین پرش از منبع به مقصد می باشد. هدف حداقل سازی این مصرف انرژی برای هر بسته،با انتخاب مسیرهای خوب می باشد. توجه شود که کمینه کردن تعداد پرش ها ، همیشه به این هدف نمی رسد چراکه ممکن است مسیر با پرش های کم، شامل پرش ها با توان ارسال بالا برای پوشش فاصله های زیاد ،باشد . به مدل مستقل از فاصله ، با جابجایی ثابت در مصرف انرژی نیز دقت داشته باشید. به هر حال این معیار به سادگی می تواد در الگوریتم های استاندارد مسیریابی ، تعبیه شود. بیشینه کردن عمر شبکه . وظیفه ی WSN انتقال داده نیست بلکه مشاهده (و احتمالا کنترل) می باشد. بنابراین انتقال موثر از لحاظ انرژی توانایی و نقطه ی مثبتی برای رسیدن به سرانجام است و غایت واقعی باید به نوعی بهینه سازی باشد: شبکه باید قادر به انجام وظایف خود تا حد ممکن باشد. چه اتفاقی به پایان عمر شبکه می انجامد چندان واضح است و چندین انتخاب وجود دارد. زمانی که اولین نود خراب می شود. زمانی که نقطه ای بدون پوشش بوجود می آید. زمانی که شبکه تکه تکه می شود(یعنی دو نود داریم که دیگر نمی توانند با هم ارتباط برقرار کنند). هر یک از این روش ها ، راه حل های متفاوتی را می طلبند. مثلا برای تکه شدن شبکه ، نودها در کمینه کات ست های خود باید دارای مصرف انرژی یکسان باشند تا زمان تکه شدن بیشینه شود. گرچه ممکن است راه حل غیر ممکن باشد. برای نمونه، بیشینه کردن زمان تکه شدن شبکه مسئله ی NP-complete می باشد*. بدلیل این محدودیت های تئوریکی ، فقط راه حل های تقریبی ، درعمل مفید خواهند بود. مسیریابی با در نظر گرفتن انرژی باطری موجود. همچنان که بیشینه کردن عمر شبکه هدف مفیدی به نظر می رسد، در نگاه اول مشخص نیست که چگونه با مشاهده ی پارامترهای واقعی به این هدف می توان رسید. از آنجا که انرژی باطری ها محدود می باشد می توان از این معیار برای تصمیم گیری های مسیریابی استفاده کرد. از جمله انتخاب ها برای این مورد به موارد زیر میتوان اشاره کرد. مسیریابی با در نظر گرفتن بیشینه سازی ظرفیت باطری موجود . یعنی مسیری انتخاب شود که جمع انرژی موجود در مسیر ، بیشینه باشد. مسیریابی با کمینه کردن هزینه باطری ([30]MBCR). به جای نگاه کردن به مجموع انرژی موجود ، این روش به "بی میلی" یک نود برای مسیریابی ، توجه دارد. بی میلی با کاهش انرژی ،افزایش می یابد، مثلا بی میلی با کاهش انرژی ممکن است رابطه عکس داشته باشد. بنابراین هزینه مسیر جمع این روابط معکوس است و مسیر با کمترین هزینه انتخاب می شود. کمینه کردن تغییرات در سطح توان. در این روش مسیر به گونه ای انتخاب می شود که تعییرات در سطوح باطری بین مسیر های مختلف کم شود. مسیریابی با کمینه کردن توان ارسالی(MTRP) . در این روش ، به حالتی که چندین نود مستقیما به مقصد ارسال دارند و تداخل حاصل ،توجه می شود. یک انتقال وقتی موفق است که نسبت سیگنال به نویز آن از آستانه ای بیشتتر شود. در اینجاهدف تخصیص توان ارسالی به هر فرستنده است به نحوی که تمامی ارسال ها موفق باشند و توان کل نیز کمینه شود. از آنجا که هر یک از این روش ها ، اهداف متفاوتی دارند،مقایسه بین این مفاهیم مشکل است . توجه شود که اگر چه بیان این اهداف ساده می باشد، ولی پیاده سازی آنها به شکل توزیعی با توجه به موازنه ی سربار جمع آوری اطلاعات با کارایی بدست آمده از روش های هوشمند مسیریابی، کار مشکلی می باشد. در بخش بعد مروری بر پروتکل های چند پخشی خواهیم داشت. چند پخشی چند پخشی ارسال داده به زیر مجموعه ای از آنها که معمولا شناخته شده است، می باشد. به جای چندین ارسال تک پخشی، مسیر یابی چند پخشی ، کمک به حداقل سازی پارامتر های شبکه چون مصرف پهنای باند، پردازش ارسال کننده و روتر ، و تاخیرات تحویل می کند. همچنین هزینه ی ارتباطاتی که یک داده را به چندین گیرنده ارسال می کنند را کاهش می دهد. مسئله ی چند پخشی در گراف G=(V,E) با تعدادی منبع و هر منبع مجموعه ای از مقصد ها برای i=1,..,n می باشد که معمولا . روش های متعددی در نحوه ی ایجاد ساختار مسیریابی چند پخشی وجود دارد(مروری بر این روش ها در * یافت می شود) . در زیر مروری به این روش ها خواهیم داشت . درخت مبتنی بر منبع . اولین ایده ساخت درختی با ریشه ی منبع است که شامل تمامی مقاصد و درصورت نیاز برای ساخت درخت ،شامل نودهای دیگر، می باشد.انتخاب درخت(از بین درخت های متعدد ممکن) براساس هدف بهینه سازی که بیانگر هزینه ی پیوندهاست تعیین می شود. برای هر منبع،هزینه ی کلی را کمینه کن. این روش سعی در پیداکردن درختی دارد که جمع هزینه ی تمامی پیوندهای آن کمینه است. این مسئله ی درخت steiner می باشد که به خوبی با مسئله ی مسیریابی چند پخشی مطابقت دارد. این مسئله NP-complete می باشد(با تقریب ). توجه کنید که مسئله همه پخشی با هزینه ی حداقل برابر با مسئله درخت پوشاست (مگر آنکه "سود بی سیمی" در نظر گرفته شود)که در واقع در زمان چند جمله ای قابل حل است. برای هر منبع ، هزینه بیشینه به هر مقصد را کمینه کن. به دلیل پیچیدگی روش بهینه سازی قبل ، هدف بهینه سازی دیگری می توان در نظر گرفت و آن کمینه کردن هزینه ها به هر مقصد به طور مجزا می باشد. در واقع این روش مسئله چند پخشی را به چندین مسئله ی تک پخشی تبدیل می کند که با هر الگوریتم مسیریابی چون دیکسترا قابل حل است. شکل 1-5 نمایانگر تفاوت بین این دو مسئله بهینه سازی و درخت حاصل می باشد. شکل1-5.تفاوت بین درخت steiner و درخت کوتاهترین مسیر(پیوندهای پررنگ قسمتی از درخت می باشند) درخت مشترک مبتنی بر هسته . ایجاد و نگهداری درخت های منحصر به هر منبع ، باعث ایجاد سربار بالا می شود. اگر فقط یک درخت ایجاد کنیم این سربار کاهش می یابد- این روش به خصوص وقتی که مقاصد تمامی منابع یکسان باشند ، نوید دهنده است. عیب آن اینجاست که برای هر منبع در مقایسه با درخت مبتنی بر منبع، مسیر به مقصد ممکن است کوتاهترین مسیر نباشد. برای اشتراک درخت بین چندین منبع ، یک نود نماینده در شبکه انتخاب می شود (نه لزوما نود منبع یا مقصد) و از این نود ، درختی ساخته می شود که شامل تمامی مقاصد می باشد. این درخت بین تمامی منابع به اشتراک گذاشته می شود . انتخاب این نود هسته نیز NP-complete می باشد و اهداف بهینه سازی شبیه به درخت مبتنی بر منبع را می توان برای آن در نظر گرفت. با این مفهوم درخت مشترک ، نود هسته مطمئنا تنها نقطه ی خرابی خواهد بود. برای حل این مشکل از درخت های مشترک چند هسته ای نیز پیشنهاد شده اند. مش . گرچه درخت ها از لحاظ سربار مسیریابی بهینه می باشند ،افزونگی در آنها وجود ندارد. خرابی تنها یک پیوند ساختار اتصالات درخت رااز بین می برد. گرچه اضافه کردن پیوند ها به درخت برای بدست آوردن افزونگی ، خواص اساسی آن چون نداشتن حلقه را از بین می برد. ساختار حاصل مش * می باشد و ساختار پیچیده تری برای ارسال نیاز دارد. شکل1-6.مروری بر روش های ممکن در مسیریابی چند پخشی برای هر یک از این روش ها، پروتکل های مختلفی طراحی شده است . برای توضیح بیشتر، خواننده را به مرجع ،ارجاع می دهیم. [1] Error [2] Fault [3] Diversity [4] Address-Centric [5] Data-Centric [6] Denial Of Service [7] First Path [8] HandShaking [9] 1-hop BroadCast [10] Selective Send [11] Initiator [12] I Am Alive [13] Flooding [14] End-to-End [15] Event-to-End [16] In-Network Proccessing [17] Impersonation [18] Multihop network [19] forwarding [20] gossiping [21] Controlled flooding [22] cost [23] Table-driven [24] proactive [25] conservative [26] On-demand [27] unicasting [28] broadcasting [29] multicasting [30] Minimum battery cost routing http://networkclass87.blogfa.com/post-13.aspx http://mhporojeh.iranblog.com/ www.saze20.ir