Actual network size depends on the application and the protocols developed for the routing for this kind of networks should be scalable and efficient. Each routing protocol should support small as well as large scale networks very efficiently. As the number of node increase, it increases the management functionality of the network. Graph theoretic approach traditionally was applied to networks where nodes are static or fixed. In this paper, we have applied the graph theoretic routing to MANET where nodes are mobile. Here, we designed all identical nodes in the cluster except the cluster head and this criterion reduces the management burden on the network. Each cluster supports a few nodes with a cluster head. The intracluster connectivity amongst the nodes within the cluster is supported by multi-hop connectivity to ensure handling mobility in such a way that no service disruption can occur. The inter-cluster connectivity is also achieved by multi-hop connectivity. However, for inter-cluster communications, only cluster heads are connected. This paper demonstrates graph theoretic approach produces an optimum multi-hop connectivity path based on cumulative minimum degree that minimizes the contention and scheduling delay end-toend. It is applied to both intra-cluster communications as well as inter-cluster communications. The performance shows that having a multi-hop connectivity for intra-cluster communications is more power efficient compared to broadcast of information with maximum power coverage. We also showed the total number of required intermediate nodes in the transmission from source to destination. However, dynamic behavior of the nodes requires greater understanding of the node degree and mobility at each instance of time in order to maintain end-to-end QoS for multi-service provisioning. Our simulation results show that the proposed graph theoretic routing approach will reduce the overall delay and improves the physical layer data frame transmission

چکیده

 سایز واقعی شبکه بستگی به کاربرد دارد و پروتکل های توسعه داده شده برای مسیر یابیِ این نوع از شبکه ها باید مقیاس پذیر و کارا باشند. هر پروتکل مسیریابی باید شبکه های با مقیاس کوچک را به خوبی شبکه های با مقیاس بزرگ به صورت کاملا کارا حمایت کند. با افزایش تعداد گره ها، عاملیتِ مدیریتِ شبکه افزایش می یابد. روش نظریِ گراف عموما به شبکه هایی که گره های ایستا (ثابت) دارند، اعمام می شود. در این مقاله، ما مسیر یابی نظریِ گراف را به مانت اعمال کرده ایم، در حالی که گره ها متحرک هستند. در اینجا، ما تمام گره های یکسان را در داخل خوشه، و مجزا از سرخوشه مشخص کرده ایم، که این معیار فشارِ مدیریتِ شبکه را کاهش داده است. هر خوشه تعداد کمی گره را با یک سرخوشه حمایت می کند. اتصالات درون-خوشه ای بین گره های داخل خوشه توسط اتصالات چند هاپه حمایت شده است تا بررسی تحرک را طوری امکان دهد که هیچگونه اختلال سرویس دهی ای پیش نیاید. اتصالات داخل خوشه ای نیز توسط اتصالات چند هاپه فراهم شده اند. هرچند، برای ارتباطات برون-خوشه ای، فقط سرخوشه ها متصل شده اند. این مقاله روش نظری گراف را نشان می دهد که یک مسیر اتصال چند هاپه ی بهینه را بر مبنای کمترین درجه ی تجمعی ایجاد می کند، که تداخل و تاخیر زمانبندی پایان-به-پایان را کمینه می کند. این به ارتباطات درون-خوشه ای و ارتباطات برون-خوشه ای اعمال شده است. عملکرد نشان می دهد که داشتن یک اتصال چند هاپه برای ارتباطات درون-خوشه ای، در مصرف توان، در مقایسه با پخش اطلاعات با بیشترین پوشش توانی، بهتر عمل می کند. همچنین تعداد کل گره های میانی مورد نیاز در ارسال از منبع به مقصد را نشان داده ایم. هرچند، رفتار دینامیکِ گره ها نیاز به درک بیشتری از درجه و تحرک گره در هر فاصله ی زمانی به منظور نگهداری QoS پایان-به-پایان برای نظارت خدمات چندگانه، دارد. نتایج شبیه سازی ما نشان می دهد که روش مسیریابی نظری گرافِ پیشنهادی، تاخیر کل را کاهش داده و ارسال لایه ی فیزیکی فریم داده را بهبود می بخشد.

1-مقدمه

شبکه‌های بی‌سیم موردی متحرک (مانت) ]1 [اصولا بدون ساختار توصیف شده و در ایستگاه های پایه یا برج ها استفاده نمی شود. این شبکه می تواند به عنوان یک سیستم از گره های دینامیک متحرکِ بدون نام تعریف شود که بر روی لینک های بیسیم و بدون هیچگونه پیش نصب زیرساختاری ارتباط برقرار می کنند]2[. مستقر کردن شبکه آسان است. شبکه از لحاظ پهنای باند و توان محدود است و هنوز انتظار می رود که نظارت چند-سرویسه را با نظارت کیفیت سرویس پایان-به-پایان برای کاربران هدف فراهم کند...