فنی تخصصی

مقدمه

شبکه های ad hoc موبایل از مجموعه ای از گره های متحرک بیسیم تشکیل شده است که به طور پویا یک شبکه موقت را شکل می دهد. این گره ها می توانند به دلخواه خود بدون هیچ مکانیزم مدیریت متمرکزی حرکت کنند. توپولوژی این نوع شبکه ها به علت حرکت گره ها می تواند بسیار پویا باشد. در محیط ad hoc ، host های شبکه در گروه ها کار می کنند، تا کار داده شده را انجام دهند بنابراین multicast نقش مهمی را در شبکه های ad hoc ایفا می کند.

پروتکل های multicast که برای شبکه های ad hoc بیسیم وجود دارد به Tree-based و Mesh-based دسته بندی میشود. در پروتکل Tree-based تنها یک مسیر بین یک جفت مبدا و مقصد است که دو رویکرد در این پروتکل وجود دارد:

Source-Tree-based :هر گره منبع یک درخت توزیع شده ای را برای هر عضو گروه می سازد. معمولا مسیر بین منبع و هر عضو کوتاهترین نیست.

Shared-Tree-based : فقط یک درخت multicast برای گروه multicast ساخته می شود که همه گره های منبع را شامل می شود. هر منبع این درخت را برای راه انداختن multicast )ایجاد درخت (multicast استفاده می کند.

مسیریابی multicast ِ Tree-based برای شبکه های بیسیم و اینترنت به خاطر سادگیشان بسیار جذاب است. در این مقاله ما یک پروتکل مسیریابی multicast جدید را پیشنهاد می کنیم به نام:

Weight-Based Clustering Multicast Protocol for Mobile Ad hoc Networks (wcmp)

(پروتکل multicast خوشه بندی بر اساس وزن برای شبکه های ad hoc موبایل)

هدف این کار بهبود دادن و بهتر کردن کارایی multicast در شبکه های ad hoc است.

پروتکل WCMP

در این پروتکل روش کار به این صورت است: در ابتدا منبع درخت multicast را ایجاد می کند سپس با استفاده از الگوریتم وزن دار تعدادی گره را در درخت به عنوان clusterhead انتخاب می کنیم.

ایجاد یک درخت multicast توسط منبع multicast آغاز می شود و با پیام Ack تمام می شود. منبع یک packet ِ Join-Tree-Request  را به هر گره می فرستد. وقتی یک گره متحرک به گروه multicast  تمایل پیدا می کند، packet ِ Join-Tree-Request را دریافت می کند و به منبع با پیام Join-Ack پاسخ میدهد. شکل زیر ایجاد درخت multicast را تشریح می کند. منبع s ایجاد درخت را با فرستادن پیام Join-Tree-Request به همه گره های متحرک آغاز می کند. گره های D , B , A به گروه multicast  تمایل پیدا می کنند و به منبع با پیام Join-Ack جواب می دهند.

هر گره به یک cluster که توسط clustrehead آن اداره می شود، متعلق است.

 clusterhead اطلاعات و ارتباطات اعضای گروه را نگهداری و ضبط میکند و استفاده می شود که هزینه سربار و ازدست دادن packet ها را کاهش بدهد. علاوه برآن ما باید در انتخاب تعداد Clusterhead ها دقت کنیم تا پیغام های کنترلی Clusterhead باعث کاهش through put نشود.

هر گره ارزش وزن های متفاوتی دارد.که با Wi مشخص می شود. 3 پارامتر در محاسبه Wi استفاده می شود:

1.     تعداد گره های مرزی از i در داخل 2-hop که به شکل BN(i) مشخص می شود. (برگ های درخت)

2.     تعداد گره های همسایه برای i در داخل 2-hop که i را هم شامل می شود و به شکل NN(i)  مشخص می شود.

3.     درجه i که به شکل Deg(i) مشخص می شود. اگر Deg(i) یک باشد، دراین صورت i یک گره مرزی نامیده می شود.

این 3 پارامتر را در تابع وزن گذاشته و وزن هر گره را بدست می آوریم:

Wi = 0.7x BN(i) + 0.2x NN(i)  + 0.1x Deg(i)

بعد از محاسبه وزن گره ها برخی از آنها را به عنوان clusterhead انتخاب می کنیم:

گام اول: گره ای که وزن بیشتری از بقیه گره ها دارد را به عنوان clusterhead در آن ارتفاع از درخت multicast انتخاب کنید.

گام دوم: وقتی یک گره به عنوان clusterhead انتخاب می شود، همه گره های زیرینش را اداره می کند.

گام سوم: اگر دو گره clusterhead همسایه باشند و در یک cluster از درخت multicast  باشند، گره ای را انتخاب می کنیم که به منبع نزدیکتر باشد.

گام چهارم: اگر درجه گره ای یک است یا فقط یک گره در یک سطح وجود دارد، ما هیچ clusterhead ای در این سطح از درخت multicast انتخاب نمی کنیم.

گام پنجم: بقیه گره های بدون مراقبت توسط منبع اداره می شوند. بنابراین منبع نیز یک clusterhead است.

شکل زیر درخت multicast را نشان می دهد به طوریکه s ریشه است.

 مطابق با تابع وزن ماگره A و B درجه یکسانی در height=1 دارند. BNA گره های M , L , J در داخل 2-hop است.(باید دید به کدام گره مرزی با حداکثر دو پرش از A می توان رسید) بنابراین BNA سه است. NNA گره های E , M , J , B , I , C , L , S , A در داخل 2-hop است. بنابراین مقدار NNA  نه است. (باید دید به کدام گره با حداکثر دو پرش از A می توان رسید)

BNB گره های J , H , G , F است پس مقدار BNB چهار است. NNB گره های A , I , G , F , S , D , H , B است پس مقدار NNB هشت است. گره های D , C نیز دارای درجه یکسانی در height=2 هستند. پس تعداد گره های مرزی و گره های همسایه D , C را هم محاسبه میکنیم.

در اینجا NN , BN را در فرمول تابع وزن گذاشته و وزن هر گره را محاسبه می کنیم:

BNA : J , L , M                                               BNA = 3

NNA : A , S , L , C , I , B , J , M , E              NNA = 9

WA = 0.7x 3 + 0.2x 9 + 0.1x 3 = 4.2

BNB : F , G , H , J                                         BNB = 4

NNB : B , H , D , S , F , G , I , A                 NNB = 8

WB = 0.7x 4 + 0.2x 8 + 0.1x 3 = 4.7

WC = 0.7x2 + 0.2x7 + 0.1x3 = 3.1

WD = 0.7x3 + 0.2x6 + 0.1x3 = 3.6

اکنون می خواهیمClusterhead  را با توجه به وزن گره هایی که قبلا به دست آوردیم، پیدا کنیم. O , N نمی توانند clusterhead باشند چون فقط یک گره در آن سطح هستند( طبق گام چهارم). در سطح 3 درجه E از همه بیشتر است، پس clusterhead است. در سطح 2 D , C  بیشترین درجه را دارند، پس وزن آن ها را مقایسه می کنیم که D وزنش بیشتر است پس clusterhead است. در سطح یک، B , A بیشترین درجه را دارند ولی B وزنش بیشتر است پس به عنوان clusterhead انتخاب می شود. و چون D , B دو clusterhead در یک خوشه هستند،گره ای را که به منبع نزدیکتر است انتخاب می کنیم.( طبق گام سوم)

بعد از انتخاب clusterhead منبع به طور منظم یک packet ِ CHREQ (clusterhead Request) را می فرستد تا clusterhead را پیدا کند. packet ِ clusterhead Request به این صورت نمایش داده می شود.  CHREQ(S , HP , FG) که S منبع را نشان می دهد. HP  ، History Path را نشان می دهد که این یک مسیری است که packet در آن جا به جا شده است. FG  که flag است و توسط گره ای استفاده می شود که می خواهد نشان بدهد یک clusterhead است.

شکل فوق عملیات wcmp را شرح می دهد. وقتی که clusterhead های B , A , S تعیین می شوند ، منبع S ، CHREQ را به B , A می فرستد تا از مسیرهای S تاA  و S تا B اطلاع پیدا کند. وقتی گره A پیام CHREQ را دریافت می کند، FG را به TRUE ، set می کند و پیام CHREP را به منبع می فرستد.  وقتی منبع S پیام CHREQ را به B می فرستد، مسیری که حرکت داده شده در history path ضبط می شود . بعد از اینکه B پیام CHREQ را دریافت کرد، FG را به True ، Set می کند و CHREP را در طول history path به منبع S می فرستد.