انواع الگوریتم های مسیریابی چندگانه

تکنیک های مکان یابی شبکه حسگر بی سیم (ادامه)

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

تکنیک های اندازه
گیری

تکنیک های اندازه
گیری در مکان یابی شبکه حسگر بیسیم بطور کلی میتواند به سه دسته طبقه بندی شود:
اندازه گیری های AOA،
اندازه گیری های وابسته به فاصله و تکنیک های شکل دهی RSS.

اندازه گیری های
زاویه ی ورود.

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

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

 

یکی دیگر از
روشهایی که برای مواجهه با مشکل نوسان شدت سیگنال بسیار مورد استفاده قرار میگیرد
بکارگیری حداقل دو (اما معمولا حداقل چهار) آنتن ایستای آگاه از الگوهای
ناهمسانگرد است. از روی هم افتادگی این الگوها و مقایسه­ی شدت سیگنال دریافتی از
هر آنتن در یک زمان جهت فرستنده بدست می­آید، حتی زمانی که شدت سیگنال تغییر کند.
میزان سازی درشت با استفاده از اندازه­گیری اینکه کدام آنتن قوی ترین سیگنال را
دارد انجام می­شود، و  و بدنبال آن بوسیله­ی
میزان سازی مناسب که مقایسه بین پاسخ­های دامنه است. بدلیل خطاهای کوچک در
اندازگیری توان دریافتی می­تواند منجر به خطای اندازگیری AOA
بزرگی شود، دقت اندازه گیری نوعی برای چهار آنتن 10 تا 15 درجه است. با شش آنتن
این میتواند تا 5 درجه و با 8 آنتن تا 2 درجه بهبود یابد.

دسته­ی دوم از
تکنیک های اندازه گیری به فاز تداخل مشهور هستند[7]،
اندازه ی AOA
را از اندازگیری فاز تفاوت­های درون جبهه ی موج رسیده بدست می­آورد. نوعا در این
دسته نیاز به یک آنتن گیرنده ی بزرگ (متناسب با طول موج سیگنال فرستنده) یا یک
آرایه­ی آنتنی دارد. شکل 2 یک آرایه­ی آنتنی که از N
عنصر آنتن تشکیل شده است نشان می­دهد. عناصر آنتنی مجاور با فاصله ی یکسان d
از یکدیگر جدا شده­اند. فاصله­ی بین یک فرستنده بیسار دور از آرایه­ی آنتنی و عنصر
آنتن iام بوسیله­ی فرمول
زیر قابل تخمین است. که دراینجا R0
فاصله­ی بین فرستنده و عنصر آنتن 0 و h پرتوی فرستنده نسبت به آرایه­ی آنتن است.

سیگنال­های
دریافتی فرستنده بوسیله­ی عناصر آرایه­ی مجاور فاز تفاوت زیر را دارند،که به ما
این اجازه را می­دهد تا وضع فرستنده را از روی اندازگیری فاز تفاوت بدست آوریم.
این روش بخوبی برای SNR
های بالا کار می­کند اما ممکن است با وجود تداخل­های کانال مشترک قوی و/یا سیگنال­های
چند مسیری به شکست منجر شود[7].
دقت اندازگیری های AOA
بوسیله­ی رهنمودهای آنتن محدود می­شود. چگونگی بدست آوردن دقت اندازه گیری های AOA
در حضور خطای سایه و چندمسیری به یک موضوع پرجاذبه برای تحقیقات بدل شده است.
اندازگیری های AOA
وابسته به جهت دید[1] مستقیم از فرستنده به گیرنده
است.

هرچند که یک عنصر
چندمسیری ممکن است بعنوان یک سیگنال رسیده از یک جهت کاملا متفاوت دیده شود و می­تواند
منجر به خطاهای بسیار بزرگی در اندازگیری های AOA
شود. مسائل چند مسیری در اندازگیری های AOA با استفاده از الگوریتم های حداکثر احتمال
[2]
مرتفع شده است[7]. الگوریتم های حداکثر احتمال متفاوتی در مقالات علمی
ارائه شده است که فرضیات مختلفی را درباره­ی خصوصیات احتمالی سیگنال های رخ
داده
در نظر میگیرند[8-10].
می­توان آنها را در دو دسته­ی روشهای حداکثر احتمال قطعی و غیرقطعی طبقه
بندی
کنیم. نوعا روشهای حداکثر احتمال AOA
را برای هر مسیر جداگانه در یک میحط چند مسیری تخمین می زنند. پیاده سازی
این
روشها از نظر محاساتی دشوار است و نیاز به جستجوی چندبعدی پیچیده دارد.
ابعاد
جستجو برابر با کل تعداد مسیرهایی است که توسط تمام سیگنالهای دریافتی
گرفته شده­اند[7]. مسئله همچنان پیچیده می­باشد بوسیله­ی این واقعیت که
تعداد کل مسیرها یک مقدم ناشناس است و باید تخمین زده شود. در تضاد با
روشهای
حداکثر احتمال اخیر، که فرض می­کنند سیگنال ورودی یک فرآیند تصادفی ناشاخته
است،
دسته­ی دیگری از روشهای حداکثر احتمال [11-13]
فرض می­کنند که ساختار شکل موج برای گیرنده شناخته شده است. این فرض در
بعضی سیستم
های ارتباطی امکان پذیر است چراکه قالب مودلاسیون برای گیرنده شناخته شده
است و
اکثر سیستم ها با یک دنباله­ی یادگیری در دیباچه مجهز شده اند. داده های
اضافی
منجر به بهبود دقت اندازگیری های AOA
یا ساده کردن محاسبات می شود.

هنوز در دسته­ی
دیگر روشهای اندازه گیری AOA
براساس اصطلاحا الگوریتم های زیر-فضا پایه باقی مانده است. مشهورترین و بهترین
روشها در این طبقه بندی MUSIC
[3](دسته بندی سیگنال چندمسیری) و ESPRIT[4](تخمین پارامترهای سیگنال با تکنیک های تغییر ناپذیری
چرخشی) [15,16]. این الگوریتم های خود تجزیه وتحلیل براساس جهت یافت
شده از یک فرمول فضای بردار استفاده می­کنند، که از مزیت مدل داده­ی پارامتریک
اساسی برای مشکل آرایه­ی حسگر استفاده بهره می­یرد. آنها به یک آنتن چندآرایه­ای
برای ساخت یک ماتریس همبستگی  با استفاده
از سیگنالهای دریافتی توسط آرایه نیاز دارند. بردارهای سیگنال اندازگیری شده که در
M
عنصر آرایه دریافت شده اند، بعنوان یک بردار فضای M
بعدی بصری سازی می شوند.

 

با بکارگیری
یک ماتریس همبستگی خود تجزیه، فضای بردار به زیرفضاهای نویز و سیگنال تقسیم
می­شود.
سپس الگوریتم MUSIC بدنبال تهی­ها
در مربع برزگی طرح بردار جهت برروی زیرفضای نویز می­گردد. تهی­ها یک تابع
از زاویه­ی
ورود است، که از طریق آن زاویه­ی ورود قابل تخمین است. برای آرایه­های خطی،
Root-MUSIC [18]، ریشه­ی چندجمله­ای نسخه­ی MUSIC، توانایی تمیز MUSIC را
بهبود می­بخشد. یک نسخه­ی وزندار MUSIC، WMUSIC
[19] توسعه­ای را در توانایی شناسایی در
مقایسه با MUSIC اصلی بوجود آورده است. ESPRIT
[15,16] براساس تخمین پارامترهای سیگنال در
برابر تکنیک های تغییر ناپذیر چرخشی است.



مسیریابی در شبکه های بیسیم حسگر – قسمت چهارم

از بهترين طبقه بندی های
پروتکل­هاي مسيريابي شبکه­های حسگر
، طبقه­بندي
ارائه شده توسط آقايان
اکايا
و يانيس مي
باشد.

اين طبقه ­بندي،
پروتکل­هاي مسيريابي را با توجه به نحوه عملکرد گره­ها، اطلاعات در دسترس هر گره و
اهداف شبکه به چهار دسته کلي: “داده محور”، “سلسله مراتبي”،  “بر اساس موقعيت” و  “آگاه از کيفيت سرويس و جريان
شبکه” تقسيم مي­کند.

پروتکل­هاي
مسيريابي داده محور

در بسياري از
کاربرد­هاي شبکه­هاي حسگر اختصاص يک شناسه عمومي به گره­ها امکانپذير نيست. اين
وضعيت باعث مي­شود که براي پرسوجوهاي مختلف انتخاب يک مجموعه خاص، سخت باشد.
بنابراين داده از هر گره به محدوده گستر
ده گره­ها انتقال مي­يابد که افزونگي
زياد
ي را در
بر مي­گيرد
‌و
باعث مي­شود که کارائي از لحاظ مصرف انرژي پايين بيايد.
اين پروتكل‌هاي مسيريابي كه داده محور نام
دارند
با
مسيريابي­هاي سنتي که بر پايه آدرس
هستند
متفاوت
مي‌باشند.
در مسيريابي­هاي داده محور معمولا گره مرکزي پرسش­هايش را به منطقه­هاي معين مي­فرستد
و براي دريافت داده از گره­هاي موجود در آن ناحيه منتظر مي­ماند. بعد از اينکه
پاسخ پرسش به دست آمد، پاسخ در
داخل بسته داده به گره مرکزي ارسال مي­شود. پروتکل­هاي ارائه شده زيادي را مي­توان
در دسته پروتکل­هاي داده محور قرار داد که از مهمترين آنها مي­توان به پروتکل­هاي
“انتشار سيل­گونه”
، “شايعه­پراکني”، SPIN ، Directed Diffusion ، Flooding ، EAR و … اشاره کرد.

 

پروتکل­هاي مسيريابي سلسله مراتبي

در مسيريابي
سلسله مراتبي، گره­ها به خوشه­هاي منطقي تقسيم مي­شوند. در هر خوشه
یک گره­ سرخوشه و گره­هاي
ديگر به عنوان اعضای خوشه در نظر گرفته مي­شوند. اعضای خوشه اطلاعات مورد نظر را
با توجه به کاربرد از محيط به دست مي­آورند و سپس اين اطلاعات را به سرخوشه ارسال
مي­کنند. سرخوشه نيز با جمع­آوري اين اطلاعات آنها را به گره مرکزي مي­فرستد.
اکثر پروتکل­هاي سلسسله مراتبي داراي دو مرحله براي مسيريابي هستند
. مرحله اول انتخاب سرخوشه و
مرحله دوم مسيريابي مي­باشد. مسيريابي سلسله مراتبي يک راه موثر براي کاهش پيغام­هاي
ارسالي به ايستگاهاي اصلي و در نتيجه افزايش طول­عمر شبکه مي­باشد.
پروتکل­هاي
زيادي را مي­توان به اين دسته اختصاص داد که از جمله مي­توان به
LEACH، PEGASIS
، TEEN، APTEEN
، AIMRP، HEED
و اشاره
کرد.

پروتکل­هاي مسيريابي براساس موقعيت

بيشتر پروتکل­هاي مسيريابي نياز دارند كه گره­هاي اطلاعات موقعيت خود را داشته
باشند. در بيشتر موارد اطلاعات موقعيت به منظور محاسبه فاصله بين دو گره خاص براي
تخمين مصرف انرژي نياز است. با استفاده از اطلاعات موقعیتی می‌توان راهکارهای موثر
مسیریابی ارائه داد که در مصرف انرژی صرفه­جویی موثری انجام دهند.

آگاهي از
موقعيت مي­تواند به وسيله وسايل فيزيکي مانن
GPS و يا
الگوريتم اکتشاف توپولوژي به دست آيد.
تا كنون پروتکل­هاي مسيريابي بر اساس
موقعيت زيادي ارائه شده است که مي­توان به
MECN ، GAF، GEAR، PGR و
… اشاره کرد.
توضيح برخي از اين پروتکل­ها در ذيل آمده است.

پروتکل­هاي مسيريابي آگاه از
کيفيت سرويس­دهي و جريان شبکه

الگوريتم‌ها نيز موارد ديگري همچون کيفيت سرويس و جريان شبکه را مدنظر قرار
داده‌اند. پروتکل­هاي آگاه از کيفيت سرويس‌دهي نياز­هاي تاخير انتها به انتها، طول­عمر
شبکه و … را بررسي مي­کنند. پروتکل­هايي همچون “جمع­آوري داده با حداکثر
طول­عمر”، “ارسال با حداقل هزينه”،
SAR و در اين دسته­بندي
قرار دارند. توضيح برخي از اين پروتکل­ها در ذيل آمده است.

پروتكل ارسال با حداقل هزينه

پروتكل “ارسال با حداقل هزينه”، هزينة ارتباطي را بر مبناي سه
فاكتور تأخير لينك، توان عملياتي و انرژي باقيمانده در گره بنا كرده است. الگوريتم
ارائه شده داراي دو فاز مي‌باشد. در فاز اول، گره مركزي بستة
interest را در سطح شبكه منتشر مي‌كند. هر گره، با دريافت interest هزينة خود را بر مبناي هزينة دريافتي از گره قبلي و هزينة لينك
ارتباطي محاسبه كرده و بسته را با هزينة جديد براي همسايگانش ارسال مي‌دارد. بدين
ترتيب، در پايان اين فاز، كلية گره­ها هزينة ارتباطي خود تا گره مركزي را تعيين
خواهند نمود. فاز دوم به انتقال بسته‌ها به سمت گره مركزي تعلق دارد. در اين فاز،
گره‌اي كه بسته‌اي براي ارسال دارد، هزينة ارتباطي خود تا گره مركزي را در سرآيند
بسته قرار داده و بسته را براي همسايگان خود منتشر مي‌كند. هر همساية گره، هزينة
قرار داده شده در سرآيند بسته را چك مي‌كند. در صورتي كه هزينة ارتباطي اين همسايه
تا گره مركزي از هزينة مزبور بيشتر باشد، بدون هرگونه عملياتي، بسته را حذف مي‌كند.
ولي در صورتي كه هزينة ارتباطي تا گره مركزي، كمتر از هزينة موجود در سرآيند بسته
باشد، ابتدا سرآيند بسته را تغيير مي‌دهد تا هزينة ارتباطي خود تا گره مركزي را
شامل شود، و سپس بسته را براي همسايگان خود منتشر مي‌نمايد.

پروتکل SAR

پروتکل SAR، درخت‌هائي را تشكيل مي‌دهد كه ريشة
آنها قابليت ارتباط مستقيم با گره مركزي را دارند. يال‌هاي اين درخت با در نظر
گرفتن سه عامل كيفيت سرويس، منابع انرژي در هر مسير و سطح اولويت هر بسته تعيين مي‌شوند.
بدين ترتيب، مسيرهاي متعددي از گره مركزي به سمت هريك از حسگرها به دست خواهد آمد.
در هنگام ارسال اطلاعات، يكي از اين مسيرها بر اساس كيفيت سرويس و منابع موجود روي
هر مسير انتخاب مي‌شود.



دیدگاهتان را بنویسید

نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *

Back To Top