Modeling and evaluation of RPL routing protocol by colored Petri nets
Subject Areas : ICTMohammad Pishdar 1 * , Younes Seifi 2
1 -
2 - پژوهشگاه ارتباطات و فناوری اطلاعات
Keywords: كليد واژه انگلیسیColored Petri nets, Internet of Things (IoT), Routing Protocol for LLNs (RPL),
Abstract :
The Internet of Things (IoT) is a novel and widely used idea aimed at connecting objects through communication technologies. The problem of the prior technology adaptation has always been one of the most challenging issues in this area over the years. The Recognition of Prior Learning (RPL) protocol has been proposed by scientists since 2012 as a solution for IoT routing. This protocol has been utilized by many researchers and hardware companies in the field of the mentioned technology. The present study evaluates RPL behavior from the perspective of the existence of stopping conditions, crossing multiple routes from a special route (loop conditions), and how it reacts to different inputs, while presenting a modular and readable model of this protocol.
[1] Kamble, A., Malemath, V. S., & Patil, D. (2017). Security attacks and secure routing protocols in RPL-based Internet of Things: Survey. 2017 International Conference on Emerging Trends & Innovation in ICT (ICEI). Published. https://doi.org/10.1109/etiict.2017.7977006
[2] Adat, V., & Gupta, B. B. (2017). Security in Internet of Things: issues, challenges, taxonomy, and architecture. Telecommunication Systems, 67(3), 423–441. https://doi.org/10.1007/s11235-017-0345-9
[3] Lamaazi, H., & Benamar, N. (2020). A comprehensive survey on enhancements and limitations of the RPL protocol: A focus on the objective function. Ad Hoc Networks, 96, 102001. https://doi.org/10.1016/j.adhoc.2019.102001
[4] Winter, T., Ed., Thubert, P., Ed., Brandt, A., Hui, J., Kelsey, R., Levis, P., Pister, K., Struik, R., Vasseur, JP., and R. Alexander, "RPL: IPv6 Routing Protocol for Low-Power and Lossy Networks", RFC 6550, DOI 10.17487/RFC6550, March 2012,
[5] Iova, O., Picco, P., Istomin, T., & Kiraly, C. (2016). RPL: The Routing Standard for the Internet of Things. . . Or Is It? IEEE Communications Magazine, 54(12), 16–22. https://doi.org/10.1109/mcom.2016.1600397cm
[6] Kamgueu, P. O., Nataf, E., & Ndie, T. D. (2018). Survey on RPL enhancements: A focus on topology, security and mobility. Computer Communications, 120, 10–21. https://doi.org/10.1016/j.comcom.2018.02.011
[7] Coloured Petri Nets: Modelling and Validation of Concurrent Systems by Kurt Jensen (2009–07-01). (2021). Springer
. [8] Zaitsev, D. A., & Shmeleva, T. R. (2019). Modeling With Colored Petri Nets. Automated Systems in the Aviation and Aerospace Industries, 378–404. https://doi.org/10.4018/978-1-5225-7709-6.ch014
[9] Chen, Y., Hou, K., Chanet, J., & GHOLAMI, K. (2013). A RPL based Adaptive and Scalable Data-collection Protocol module for NS-3 simulation platform. NICST 2013
. [10] Bartolozzi, L., Pecorella, T., & Fantacci, R. (2012). ns-3 RPL module: IPv6 Routing Protocol for Low power and Lossy Networks. ACM. https://doi.org/10.4108/icst.simutools.2012.247718
[11] Karkazis, P., Trakadas, P., Zahariadis, T., Hatziefremidis, A., & Leligou, H. C. (2012, June). RPL modeling in J-Sim platform. 2012 Ninth International Conference on Networked Sensing (INSS). https://doi.org/10.1109/inss.2012.6240559
[12] Tripathi, J., de Olive, J. C., & Vasseur, J. P. (2010, March). A performance evaluation study of RPL: Routing Protocol for Low power and Lossy Networks. 2010 44th Annual Conference on Information Sciences and Systems (CISS). https://doi.org/10.1109/ciss.2010.5464820
[13] Becker, M., Kuladinithi, K., & Görg, C. (2012). Modelling and Simulating the Trickle Algorithm. Lecture Notes of the Institute for Computer Sciences, Social Informatics and Telecommunications Engineering, 135–144. https://doi.org/10.1007/978-3-642-30422-4_10
[14] Kristensen, L. M., & Veiset, V. (2016). Transforming CPN Models into Code for TinyOS: A Case Study of the RPL Protocol. Application and Theory of Petri Nets and Concurrency, 135–154. https://doi.org/10.1007/978-3-319-39086-4_10
[15] Wallgren, L., Raza, S., & Voigt, T. (2013). Routing Attacks and Countermeasures in the RPL-Based Internet of Things. International Journal of Distributed Sensor Networks, 9(8), 794326. https://doi.org/10.1155/2013/794326
[16] Yu, W., Jia, M., Fang, X., Lu, Y., & Xu, J. (2020). Modeling and analysis of medical resource allocation based on Timed Colored Petri net. Future Generation Computer Systems, 111, 368–374. https://doi.org/10.1016/j.future.2020.05.010
[17] Shahidinejad, A., Ghobaei-Arani, M., & Esmaeili, L. (2019). An elastic controller using Colored Petri Nets in cloud computing environment. Cluster Computing, 23(2), 1045–1071. https://doi.org/10.1007/s10586-019-02972-8
[18] Cavone, G., Dotoli, M., & Seatzu, C. (2018). A Survey on Petri Net Models for Freight Logistics and Transportation Systems. IEEE Transactions on Intelligent Transportation Systems, 19(6), 1795–1813. https://doi.org/10.1109/tits.2017.2737788
[19] Bhandari, G. P., & Ratneshwer. (2018). Dependency-based fault diagnosis approach for SOA-based systems using Colored Petri Nets. Journal of King Saud University - Computer and Information Sciences. Published. https://doi.org/10.1016/j.jksuci.2018.12.002
[20] Kaid, H., Al-Ahmari, A., Li, Z., & Davidrajuh, R. (2019). Single Controller-Based Colored Petri Nets for Deadlock Control in Automated Manufacturing Systems. Processes, 8(1), 21. https://doi.org/10.3390/pr8010021
دو فصلنامه علمي فناوري اطلاعات و ارتباطات ایران | سال چهاردهم، شمارههاي 53 و54، پاییز و زمستان 1401 صفحات:24 تا37 |
| ||
|
| |||
Modeling and evaluation of some criteria in RPLs using Colored Petri Nets
Mohammad Pishdar *, Younes Seifi**
*Computer engineering department, Bu-Ali Sina University, Hamedan, Iran
**ICT Research Institute, Teran, Iran
Abstract:
The Internet of Things is a novel idea which is widely used to connect objects through communication technologies. The problem adapting with previous technologies has, in recent years, been one of the most challenging subjects in this regard. The RPL, since its inception in 2012, has served as a solution to routing of the Internet of Things, which is increasingly used by many researches and hardware manufactures. The current research aims to propose a modular and readable RPL model to evaluate some of the criteria in its structure using Colored Petri Net capabilities. This evaluation includes an examination of protocol discontinuation, multi-transmission of a message through a specific channel (loop condition), and reaction against various inputs. Besides structural examination, some major functional parameters including energy consumption, rates of packages received at the destination and level of control messages were investigated.
Keywords:
Colored Petri nets, Internet of Things (IoT), Routing Protocol for LLNs (RPL)
مدلسازی و ارزیابی برخی معیارها در پروتکل مسیریابی RPL به وسیله شبکه های پتری رنگی
محمد پیشدار *، یونس سیفی**
* فارغ التحصیل کارشناسی ارشد فناوری اطلاعات، دانشگاه بوعلی سینا، همدان، ایران
**استادیار پژوهشگاه ارتباطات و فناوری اطلاعات، تهران، ایران
تاریخ دریافت : 21/04/1400 تاریخ : پذیرش :04/10/1400
نوع مقاله : پژوهشی
چکیده
اینترنت اشیا یک ایده جدید و پرکاربرد با هدف اتصال اشیاء از طریق فناوریهای ارتباطی است. مشکل سازگاری با فناوری پیشین در طول سالهای گذشته همواره یکی از چالشبرانگیزترین موضوعات این حوزه بوده است. پروتکل RPL از سال 2012 به عنوان راهحلی برای مسیریابی اینترنت اشیاء توسط دانشمندان مطرح گردید. این پروتکل تا کنون مورد استفاده بسیاری از محققان و شرکتهای تولیدی سختافزاری در حوزه فناوری مذکور قرار گرفته است. پژوهش جاری ضمن ارائه یک مدل ماژولار و خوانا از پروتکل RPL به ارزیابی برخی معیارها در ساختار آن با قابلیتهای موجود در شبکههای پتری رنگی میپردازد. این ارزیابی شامل بررسی شرایط توقف پروتکل، عبور چند باره پیام از یک مسیر خاص (شرایط حلقه)، چگونگی واکنش در برابر ورودیهای مختلف است. در کنار بررسی ساختاری برخی پارامترهای مهم عملکردی نیز شامل میزان مصرف انرژی، نرخ بستههای دریافتی در مقصد و میزان پیامهای کنترلی مورد بررسی قرار گرفته است.
واژگان کلیدی: شبکه های پتری رنگی،IOT ، اینترنت اشیا ، پروتکل مسیریابی RPL، مدلسازی1
[1] نويسنده مسئول:محمد پيشدارmohamadpishdar@gmail.com
1- مقدمه
ایده اینترنت اشیا1 سالها پیش با پیشرفتهای اخیر در حوزه شبکههای بیسیم با هدف اتصال اشیا و فناوریهای ارتباطی ایجاد شد. وجود برخی ویژگیهای خاص از جمله توان پردازشی و منبع انرژی محدود در میکروکنترلرهای مورد استفاده در این فناوری دانشمندان را به سمت تطبیق روشهای موجود با اینترنت اشیاء و یا ایجاد پروتکلهای جدید سوق داد ]1[ و ]2[. یکی از این پروتکلهای جدید RPL2 نام داشته که دانشمندان به دلیل وجود مدل ترافیکی خاص در اینترنت اشیاء و همچنین محدودیتهای موجود، اقدام به طراحی آن برای شبکههای کمتوان با نرخ بالای گمشدن3 بستهها نمودند ]1[ و ]2[.
مدلسازی و ارزیابی پروتکل مسیریابی RPL با توجه به استقبال گسترده پژوهشگران میتواند بسیار پرکاربرد باشد ]3[. بر این اساس بر آن شدیم تا به ارائه یک مدل مناسب برای پروتکل مذکور و ارزیابی آن بپردازیم. مدلی که دارای شرایطی مناسب از جمله طراحی ماژولار (در سطح مناسب)، انعطافپذیری، کاربرپسندی، قابلیت توسعه و بررسی مناسب باشد. وجود برخی از ویژگیهای برجسته مدلسازی و ارزیابی در شبکه های پتری رنگی مانند قابلیت گرافیکی مناسب و ابزارهای تحلیل و تشخیص خطای قدرتمند میتواند پاسخی کارا و مفید برای این نیاز باشد. لازم به ذکر است که پارامترهای اصلی ارزیابی پروتکلهای مسیریابی نظیر معیارهایی مانند میزان مصرف انرژی، میزان پیامهای دریافتی و سربار پیامهای کنترلی در بررسی RPL بسیار مورد توجه هستند. در این مقاله از بررسی با جزئیات موارد مذکور به علت دور شدن از موضوع اصلی یعنی شبکههای پتری رنگی صرف نظر شده است. در ادامه ابتدا به تعریف مفاهیم مهم و به دنبال آن بررسی کارهای پیشین پرداخته شده است. سپس فرآیند مدلسازی و نتایج ارزیابی مدل مذکور ارائه خواهد گردید.
2– مفاهیم مهم
در این قسمت به شرح مفاهیم مهم این پژوهش پرداخته میشود.
2-1-پروتکل مسیریابی RPL
RPL از مهمترین پروتکلهای ارائه شده برای فرآیند مسیریابی در اینترنت اشیاء میباشد ]1[ و ]2[. در این پروتکل توپولوژی شبکه به صورت یک درخت بدون دور4 در نظر گرفته شده است ]2[ تا ]4[. شکلگیری این درخت به صورتی است که ابتدا گره ریشه با ارسال یک پیام DIO5 اطلاعات مربوط به پیکربندی درخت را منتشر میکند. سایر گرهها با دریافت این پیام به درخت ملحق شده و یک زمانسنج را برای انتشار مجدد اطلاعات تنظیم میکنند. در واقع هر گره با سر رسیدن مقدار زمانسنج مذکور یک پیام DIO جدید را با بروزرسانی موقعیت خود در درخت و همچنین نسخه اطلاعات دریافتی برای سایر گرهها (به صورت همه پخشی) ارسال میکند. با تکرار این عمل اطلاعات تا برگها رسیده و ساختار درخت شکل خواهد گرفت ]4,5[.
هر گره با دریافت یک پیام DIO جدید، لیست پدران خود در درخت را جهت تغییرات بررسی کرده و بهترین آنها را (از نظر هزینه) برای ارسال پیامها به ریشه انتخاب میکند. فرآیند انتخاب بر اساس یک تابع هدف6 در پروتکل RPL صورت میگیرد. این تابع با معیارهای مختلفی نظیر تعداد گامهای باقیمانده تا مقصد یا وضعیت لحظهای پیوند7ها سازگار است ]4[ تا ]6[.
موقعیت هر گره در درخت به وسیله مقدار RANK به صورت رابطه معکوس با فاصله از ریشه نشان داده میشود. در واقع هرچه از درخت دور شویم مقدار RANK نیز افزایش خواهد یافت. چگونگی تشکیل درخت DODAG در شکل شماره 1 نمایش داده شده است. در بخش a این شکل گرههای N1 الی N5 دیده میشود که قرار است یک درخت DODAG با محوریت گره ریشه N1 تشکیل دهند. گره ریشه در بخش b این شکل شروع به ارسال یک پیام DIO (شامل اطلاعات لازم نظیر مقدار Rank، نسخه درخت و مقدار کمینه افزایش مقدار Rank در هر گام) به صورت همهپخشی در محدوده بیسیم خود کرده که تنها گره N2 در این محدوده قرار داشته و آن را دریافت میکند. این کار در بخش c شکل 1 توسط گره N2 تکرار شده و پیام DIO با بروزرسانی مقدار Rank به سایر گرهها خواهد رسید که آنها نیز این فرآیند را تکرار میکنند تا درخت به صورت بهینه کامل شود. در نهایت بخش d این شکل تصویر کامل درخت مذکور را نمایش میدهد که هر کدام از گرهها مقدار Rank و بهترین والد خود را مشخص کردهاند.
در پروتکل RPL گرهها علاوه بر پیام DIO به وسیله پیام دیگری به نام DAO8 اطلاعات مربوط به خود یا زیر درخت مربوطه را به سمت بالای درخت منتشر میکنند ]4[ تا ]6[. پس از تشکیل درخت با توجه به تنظیمات موجود در پیام DIO به دو صورت اطلاعات مربوط به مسیرها میتواند ذخیره گردد ]4 [.
1- ذخیره تمام اطلاعات در ریشه : در این حالت تمام پیامها جهت یافتن مقصد به ریشه ارسال و سپس توسط ریشه مسیریابی میگردند.
2- ذخیرهی اطلاعات به صورت توزیع شده و به شکل بردار فاصله ای9 : در این حالت هر گره در درخت دارای دید محلی خود بوده و در صورت وجود مسیری به مقصد، پیام را به سمت پایین درخت و برگ ها ارسال میکند. در صورت عدم وجود مسیر نیز پیام به سمت ریشه ارسال و سپس توسط آن مسیریابی خواهد شد.
پروتکل RPL طوری طراحی شده است که هنگام وقوع ناسازگاری شرایط را به حالت صحیح بازگرداند. این فرآیند به وسیله تعمیر محلی و یا همگانی10 صورت میپذیرد. در تعمیر محلی با وقوع هر گونه خطا هنگام ارسال پیامها یا در ساختار آنها (وقوع ناسازگاری) سعی بر انتخاب مسیری دیگر خواهد شد. لازم به ذکر است که با افزایش تعداد ناسازگاریها به یک آستانه مشخص فرآیند تعمیر همگانی آغاز میگردد. در تعمیر همگانی، ریشه درخت شروع به ارسال یک پیام DIO با افزایش شماره نسخه اطلاعات مینماید. دریافت این پیام در یک گره به معنی پایان اعتبار درخت فعلی و نیاز به تشکیل ساختار درختی جدید است. بر این اساس گره مربوطه اطلاعات ذخیره شده خود را حذف و پروتکل RPL را از ابتدا اجرا مینماید. با اجرای مجدد پروتکل توسط تمام گرهها درخت از نو و با حذف ناسازگاریها بازسازی خواهد شد]4 [.
2-2- شبکههای پتری رنگی11
شبکههای پتری رنگی ابزاری قدرتمند جهت مدلسازی، به خصوص در سیستمهای همروند و همزمان میباشد ]7[ و ]8[. یکی از ویژگیهای برجسته این شبکهها، محیط گرافیکی آن بوده که از نسخه قدیمیتر آن یعنی شبکههای پتری بر جای مانده است. در شبکههای پتری رنگی از مفاهیم گرافیکی زیر استفاده میشود ]7[.
1- وضعیت12 : نشان دهندهی یک وضعیت در سیستم بوده که با دایره نمایش داده میشود. هر وضعیت تنها از نشانههایی با نوع مشخص پشتیبانی میکند.
[1] Internet of Things (IOT)
[2] Routing Protocol for Low-Power and Lossy Networks
[3] Low-Power and Lossy Networks
[4] DODAG (Destination Oriented Directed Acycle Graph)
[5] Dag Information Object
[6] Objective Function
[7] Links
[8] Destination Advertisement Object
[9] Distance Vector
[10] Global
[11] Colored Petri Net
[12] Place
شکل 1 : نحوه ی ایجاد درخت DODAGدر چهار مرحله ]5[
2- نشانه1 : اطلاعات به وسیله نشانهها در این شبکهها مدل میگردند. نشانهها در شبکههای پتری رنگی به وسیلهی دایرهی توپر کوچک نشان داده میشوند.
3- تبدیل2 : انجامدهنده یک فرآیند در سیستم بوده که با مستطیلها نمایش داده میشود. با اجرای هر تبدیل نشانههای مورد نیاز آن فرآیند مصرف شده و پس از پردازش مربوطه نتیجه مجددا در قالب نشانه به بخش دیگر تبدیل منتقل میشود (دو طرف هر تبدیل وضعیتها قرار دارند).
4- کمان3 : جهت حرکت نشانهها را در مدل با پیکانها نشان میدهد.
در شبکههای پتری رنگی انواع داده متناظر با رنگهای مختلف در نظر گرفته میشود. در این شبکه ها هر کمان تنها میتواند نشانههای همرنگ با وضعیت ورودی و یا خروجی خود را منتقل کند ]7[ و ]8[. از ویژگیهای دیگر شبکههای پتری رنگی میتوان به قابلیت مدلسازی پیمانهای اشاره کرد (طراحی سلسله مراتبی4) ]7[. علاوه بر این در شبکههای پتری رنگی ابزارهای مهمی جهت تحلیل و بررسی مدل، از جمله" بررسی فضای حالت" وجود دارد. فضای حالت5 شرایط سیستم و چگونگی رسیدن به وضعیتهای مختلف در یک مدل را برای تمام حالات ممکن نمایش میدهد (اجرای یک تبدیل وضعیت سیستم را تغییر میدهد). نمایش این فضا به صورت یک گراف جهتدار بوده که هر گره آن نماینده یک وضعیت متفاوت در سیستم است. جهت آشنایی بیشتر در شکل شماره 2 نمونهای از فضای حالت نمایش داده شده است ]7[. در این شکل:
1. مربعها نشانهندهی وضعیتهای مختلف یک مدل هستند (مربع شماره 1 نقطهی شروع است).
2. پیکانها وضعیت تبدیل به وضعیت دیگری در سیستم را از طریق رخداد یک یا چند تبدیل نشان میدهند.
3. عدد میان هر مربع شماره آن گره در فضای حالت را نشان میدهد. اعداد زیر این شماره نیز به ترتیب از چپ به راست برابر با درجه ورودی و خروجی آن گره در گراف جهتدار فضای حالت است. به عنوان مثال از گره شماره 1 میتوان به پنج وضعیت مختلف در فضای حالت رسید (وضعیتهای 2 الی 6) و همچنین از پنج وضعیت مختلف نیز امکان بازگشت به گره شماره 1 وجود دارد.
فضای حالت میتواند اطلاعات مناسبی را در مورد هر وضعیت مدل تولید کند (به عنوان مثال موجودی نشانهها در وضعیتها). علاوه بر این برخی اطلاعات تحلیلی از اجرای کلی مدل را میتوان به کمک این فضا به دست آورد. از جمله این موارد میتوان به بررسی امکان وقوع بنبست (وضعیتی که دیگر هیچ تبدیلی قابلیت اجرایی نداشته باشد) در سیستم اشاره کرد ]7[.
شکل 2 : نمونه ای از فضای حالت
2-2- اهمیت شبکههای پتری رنگی در طراحی پروتکلهای مسیریابی
استفاده از یک بستر مدلسازی و ارزیابی هنگام طراحی پروتکلها برای مقابله با اشتباهات طراحی و اعمال بهینهسازیها از اهمیت بالایی برخوردار است.پروتکلهای مسیریابی ماهیتی گسسته و توزیع شده داشته که رویداد همزمان اتفاقاتی نظیر فرآیند مسیریابی در چند بخش آن کاملا قابل تصور است. شبکههای پتری رنگی اساسا برای طراحی و بررسی چنین پدیدههایی ایجاد شده و استفاده از آن میتواند در این راستا بسیار مفید باشد. برخی از قابلیتهای کلیدی شبکههای پتری رنگی که آن را جهت به کارگیری در طراحی بعضی پروتکلها قابل توجه میکند در لیست زیر آورده شده است ]7[.
· طراحی پروتکلهای توزیع شده
· پوشش اتفاقات همزمان
· ارائه مدلسازی به صورت خوانا، ماژولار و سلسلهمراتبی (در این نوع مدلسازی زیرمدلهای دارای جزئیات بیشتر برای شکلگیری سطوح انتزاعی با یکدیگر ترکیب میشوند)
· ارائه ابزارهای مناسب برای بررسیهای فرمال
· امکان اندازهگیری تغییرات مقادیر موجود در مدل
· سادگی در طراحی و یا تغییر
3-کارهای پیشین
Bartolozzi و همکاران در پژوهش ]9[ و ]10[ پروتکل RPL را به شبیهساز NS3 اضافه کرده و عملکرد آن را از منظر ایجاد ساختار صحیح درختی و فرآیند تعمیر مورد ارزیابی قرار دادند. در این شبیهسازی (حتی در آخرین ویرایش آن) دشواری اعمال تغییرات و سطح نامناسب پیادهسازی ماژولار به خوبی قابل مشاهده است. در واقع کلاسهای ماژول RPL در NS3 وابستگی زیادی به یکدیگر داشته و بسیاری از فرآیندها در آن مستقل نیست. از دیگر مشکلات این شبیهسازی میتوان به واسط گرافیکی نامناسب و خوانایی پایین اشاره نمود. در این پژوهش همچنین به ارزیابی عملکرد RPL نیز پرداخته نشده است. در پژوهش دیگری Karsadiz و همکاران بخشی از پروتکل RPL را در بستر ابزار JSim مورد مدلسازی قرار دادند ]11[. در این مدلسازی نیاز به توسعه گرافیکال و طراحی ماژولار کاملا مشهود بوده که سبب خوانایی پایین مدل شده است. علاوه بر این ارزیابی خاصی از پروتکل RPL نیز صورت نگرفته است. در پژوهش ]12[ RPL به کمک ابزار OMNET مورد شبیهسازی و ارزیابی قرار گرفته است. در این بررسی معیارهای مختلف کارایی از جمله اندازه جداول ذخیرهسازی در گرهها و سربار پیامهای کنترلی مورد تحلیل قرار گرفته که البته هیچگونه توجهی به ارزیابی فرآیند مسیریابی RPL نشده است. در پژوهش ]13[ تنها الگوریتم قطرهچکان RPL در ابزار TOSSIM شبیهسازی شده است. در این پژوهش تاثیر زیربخش مذکور بر تاخیر ارسال پیام در ساختار RPL مورد ارزیابی قرار میگیرد.
در مرجع ]14[ محققان از امکانات توسعه گرافیکال شبکههای پتری رنگی برای مدلسازی پروتکل مسیریابی RPL و تبدیل گام به گام آن به کدهای معادل در Tiny OS (سیستمعاملی مخصوص دستگاههای بیسیم کمتوان) استفاده کردهاند. این پژوهش دارای جزئیات مناسبی از پروتکل RPL در مدلسازی نبوده و تاکید محققان بیشتر بر روی فرآیند تبدیل مدل به کد بوده است.
بر این اساس نوآوری پژوهش جاری را میتوان موارد زیر دانست:
· ارائه یک مدل ماژولار و خوانا از پروتکل مسیریابی RPL
· بررسی فرآیند مسیریابی در پروتکل RPL
· استفاده از قابلیتهای شبکههای پتری رنگی برای بررسی پروتکل مسیریابی RPL
4-مدلسازی پروتکل RPL
برای مدلسازی این پروتکل در شبکههای پتری رنگی ابتدا رفتار هر گره در درخت DODAG مدلسازی شده است. رفتار هر گره در این پیادهسازی شامل کنترل ناسازگاریها، شرکت در تعمیرات مختلف (محلی و همگانی) و مدیریت صحیح بستههای کنترلی و داده میباشد. در این مدلسازی از مجموعه رنگهای موجود در شکل شماره 3 برای تعریف انواع داده استفاده شده است. همانطور که مشاهده میشود برای هر کدام از موارد زیر نوعی رنگ در نظر گرفته شده است.
1. انواع بستههای کنترلی مورد استفاده در پروتکل RPL (پیامهای DIO، DAO و DIS)
2. فیلدهای مورد استفاده در ساختار هر بسته کنترلی
شکل 3. ColorSet ها در پروتکل RPL
در کنار رنگهای تعریفشده در شکل شماره 3 از توابع جدول شماره 1 نیز در جهت مدلسازی رفتاری پرتکل RPL استفاده شده است. در این جدول با صرف نظر از کدهای مربوط به هر تابع تنها عملکرد مربوط به هر مورد مشاهده میگردد.
در شکل شماره 4 انتزاع اول مدلسازی گرهها در پروتکل RPL قابل مشاهده است. بر اساس شکل هر گره از زیرماژولهای زیر تشکیل شده است :
1- ارسال پیام (Send): در این ماژول برای هر پیام گام بعدی در فرآیند مسیریابی مشخص و فرآیند ارسال صورت میگیرد.
2- تعمیر (Repair): در صورت وجود ناسازگاریها در پروتکل، نیاز به تعمیر و بازگردانی وضعیت فعلی به شرایط عادی است. این کار بر عهده زیرماژول تعمیر میباشد.
[1] Token
[2] Transition
[3] Arc
[4] Hierarchy Colored Petri Net
[5] State Space
شکل 4 : سطح اول انتزاع در مدل
جدول 1 : توابع مورد استفاده در مدل
3- کنترل ناسازگاری (Inconsistency Check) : این زیرماژول وظیفه مدیریت صحیح پروتکل RPL و علاوه بر آن کنترل ناسازگاریهای احتمالی را دارد.
نشانههای موجود در مربعهای مورد استفاده در این انتزاع وضعیت گرهها را در حالتهای مختلف نگهداری میکنند. وضعیتهای دوخطی موجود در هر سطح از مدل نشاندهنده پورتهای اتصال بین دو انتزاع هستند. به عبارت دیگر پورتها در بخشهای مرتبط مدل عینا تکرار شده و تبادل اطلاعات بین دو بخش از طریق آنها صورت میگیرد.
در شکل شماره 5 ماژول ارسال (سطح دوم مدل شکل شماره 4) نمایش داده شده است. در این ماژول هنگام ورود بستهها ابتدا لیست پدران DAO جهت تشخیص گام بعدی مسیریابی جستجو شده و در صورت عدم وجود گام بعدی در این لیست پیام مربوطه به پدر ارجح جهت مسیریابی (ارسال به یک گام بالاتر در درخت جهت تصمیمگیری) ارسال خواهد شد. لازم به ذکر است که دو وضعیت Dio Parents و Dao Parents برای بروزرسانی آدرسهای گام بعدی بستهها در تابع UpdateRplPacket به این ماژول اضافه شدهاند. پورتها در این شکل و انتزاع گره (شکل شماره 4) کاملا مشخص هستند. از پورت در شبکههای پتری رنگی برای اتصال بین دو انتزاع از مدل و تبادل نشانه بین آنها استفاده میشود.
شکل 5 : سطح انتزاع دوم ماژول ارسال
شکل 6 : سطح انتزاع دوم ماژول بررسی تعمیر
شکل 7 : سطح انتزاع دوم ماژول بررسی ناسازگاریها
شکل شماره 6 نشاندهنده ماژول تعمیر در پروتکل RPL میباشد.
در صورت تشخیص ناسازگاری (در یک آستانه مشخص) این ماژول وظیفه تعمیر محلی را بر عهده دارد. لازم به ذکر است که فرآیند تعمیر در این پروتکل تنها خاص این ماژول نبوده و با برخی رخدادهای دیگر نیز صورت میگیرد. به عنوان مثال با کاهش عواملی نظیر انرژی گره، مقدار RANK افزایش یافته که میتواند موجب تغییر پدر ارجح در برخی گرهها گردد. این موضوع خود به منزله تعمیر محلی است. لازم به ذکر است که دو وضعیت Dio Parents و Dao Parents برای انتخاب مسیر جایگزین از طریق تابع LocalRepair به این ماژول اضافه شدهاند. تعمیر همگانی نیز تنها توسط گره ریشه شروع و سایر گرهها با دریافت پیامهای DIO با نسخه جدیدی از اطلاعات به اجرای تعمیر همگانی میپردازند. البته برای این امر تمام نشانههای ذخیره شده در وضعیتهای مختلف گره حذف خواهند شد.
در شکل شماره 7 ماژول بررسی ناسازگاریها در پروتکل RPL مشاهده میگردد. از اصلیترین وظایف این ماژول میتوان به بررسی وجود تطابق در جهت حرکت بستهها با مقدار RANK، بررسی دریافت پیامهای تکراری DIO و یا DAO در یک گره و همچنین دریافت پیام DIO با شماره نسخه ناسازگار اشاره کرد.
این ماژول در صورت دریافت پیام DIO و یا DAO جدید، فرستنده را به لیست پدران DIO یا DAO به صورت محلی (لیست مربوط به خود گره جاری) اضافه میکند. گره مذکور در صورت کوچکتر بودن مقدار RANK فرستنده پیام DIO از مقدار RANK محلی، به عنوان پدر ارجح انتخاب خواهد شد. مقدار RANK سپس با در نظر گرفتن والد جدید بروزرسانی میشود. از دیگر وظایف این ماژول، بازارسال پیامهای DAO به پدر ارجح جهت انتشار اطلاعات مسیرهای موجود رو به پایین (مسیرهای از ریشه به سمت برگهای درخت) و همچنین افزایش مقدار Rank هنگام اتمام انرژی باتری (به معنای خروج گره از شبکه) است. ایجاد پایداری در شبکه نیز به کمک ماژول جاری صورت میگیرد. این کار با یک فناوری زمانسنج و از طریق کاهش سرعت انتشار اطلاعات کنترلی به مرور زمان اجرایی میشود ]1[.
پس از مدلسازی رفتار گرهها در RPL به مدلسازی درخت DODAG پرداخته خواهد شد. در درخت DODAG هر گره به صورت ماژول شکل شماره 4 در نظر گرفته شده و سپس ارتباط آن با سایر گرهها برقرار میگردد. به عنوان مثال مدلسازی شکل شماره 8 بر اساس ماژولهای مذکور در شکل شماره 9 نشان داده شده است.
شکل 8 : توپولوژی نمونه
5- ارزیابی پروتکل RPL
پس از مدلسازی پروتکل مسیریابی RPL در شبکههای پتری رنگی، موارد زیر را میتوان به کمک قابلیتهای این ابزار بررسی کرد. رخداد هر یک از این موارد به معنی نقص در طراحی RPL تلقی میشود.
1. وضعیت رخداد بنبست (هدف 3): در صورت اتفاق بنبست عملکرد پروتکل مسیریابی مختل خواهد شد. به عبارت دیگر در این وضعیت فرآیند مسیریابی متوقف شده و دیگر قابلیت اجرایی وجود ندارد.
2. وضعیت وقوع حلقه (هدف1): به دلیل منابع محدود موجود در دستگاههای اینترنت اشیاء وقوع یک حلقه میتواند با ایجاد سربار اضافی به حذف برخی گرهها (به علت اتمام انرژی) و یا قطع ارتباط با شبکه بیانجامد. امری که کارایی شبکه را کاهش و یا حتی مختل خواهد کرد.
3. رفتار متفاوت در مقابل ورودیهای متفاوت (هدف 2): نتیجه یکسان در دو ورودی مختلف نقطه ضعف بزرگی برای پروتکلهای مسیریابی محسوب میشود. چرا که خروجی مورد انتظار برای دو ورودی مختلف در یک پروتکل مسیریابی دو مقصد متفاوت میباشد. بر این اساس هدایت دو ورودی مختلف به یک مقصد نوعی خطا در فرآیند مسیریابی است.
علاوه بر این میتوان معیارهای مسیریابی را نیز به راحتی با شبکههای پتری رنگی مورد بررسی قرار داد. برای این منظور در پژوهش جاری معیارهایی نظیر میزان مصرف انرژی، نرخ بستههای دریافتی و میزان استفاده از پیامهای کنترلی (پیامهای سربار در شبکه) در پروتکل مسیریابی RPL مورد بررسی قرار گرفته است.
شکل 9 : توپولوژی مدل شده شکل شماره 8
شکل 10 : توپولوژی پیشنهادی
در ادامه درخت DODAG شکل 10 را به کمک مدل بخش 3 و ابزارهای موجود در شبکههای پتری رنگی بررسی میکنیم. در این شکل گره شماره 1 یا ریشه مسئول جمعآوری اطلاعات سایر گرهها است. به عبارت دیگر سایر گرهها محیط خود را بررسی کرده و اطلاعات جمعآوری شده را بر اساس پروتکل RPL به ریشه ارسال میکنند. بررسی فضای حالت این مدل در جدول شماره 2 آورده شده است. در بخش اول اطلاعات این جدول وضعیت مدل را به صورت کامل نشان میدهد (همانطور که مشاهده میگردد در این بخش وضعیت فضای حالت مدل برابر با مقدار کامل است). وضعیت کامل بدین معناست که در پروتکل RPL از هر وضعیت میتوان به وضعیتی دیگر رفته و تمام تبدیلها شرایط اجرایی را دارند. بر این اساس وضعیت رخداد شرایط بنبست وجود ندارد. مشخصه Liveness صحت دیگری برای این موضوع است. بخش Liveness در جدول 2 تبدیلهای بدون قابلیت اجرا را در فضای حالت مربوط به توپولوژی مذکور نشان میدهد. عدم وجود چنین تبدیلی در جدول 2 از عدم رخداد شرایط بنبست (هدف شماره 1) حکایت دارد.
جدول 2 : نتایج فضای حالت
آمار | ||
فضای حالت | ||
تعداد مربعها | 3628 | |
پیکانهاتعداد | 6862 | |
وضعیت | کامل | |
زمان | ثانیه1 | |
یا گراف همبند قویSCC گراف | ||
مربع هاتعداد | 3628 | |
پیکانهاتعداد | 6862 | |
زمان | ثانیه1 | |
اطلاعات فضای حالت | ||
تعداد وضعیتHOME | هیچ | |
تبدیلهای دارای ویژگیLiveness | هیچ
| |
تبدیلهای دارای ویژگی Fairness | ندارد | |
در جدول شماره 2 در کنار فضای حالت بخش دیگری تحت عنوان SCC وجود دارد. 14SCC یا گراف همبند قوی در فضای حالت، زیرمجموعهای از وضعیتهای مختلف مدل است که همه اعضای آن بتوانند به صورت حلقوی از یکدیگر قابل دسترس باشند. بر این اساس برابری تعداد گرههای گراف SCC و گرههای فضایحالت در جدول شماره 2 ( هردو 3628 گره) به معنی عدم وجود حلقه (زیرمجموعهای از وضعیتهای مختلف) در مدل پروتکل RPL میباشد.
تایید دیگری برای این موضوع ردیف مشخصه Fairness در جدول شماره 2 است. امکان اجرای بینهایت بار یک تبدیل به معنی عدم رعایت عدالت در مدلسازی است. شناسایی این نوع تبدیلها در شبکههای پتری رنگی به کمک بررسی Fairness. صورت میگیرد. مقدار هیچ در ردیف مشخصه Fairness جدول شماره 2 عدم وجود حلقه در پروتکل RPL را تصدیق میکند. در واقع حلقهها هستند که در فضای حالت امکان اجرای بینهایت بار حداقل یک تبدیل را فراهم میسازند (هدف شماره 2).
همانطور که در جدول شماره 2 مشاهده میگردد در این مدل وضعیت Home نیز وجود ندارد. این مفهوم در شبکههای پتری رنگی به معنی نبود یک نقطه مشخص پایانی برای هر دنباله از وضعیتها در فضای حالت است. به عبارت دیگر با شروع از هر وضعیت فضای حالت و اجرای تبدیلهای مربوطه نمیتوان در نهایت به یک وضعیت مشخص در مدل رسید. بنابراین رفتار پروتکل RPL بر اساس پیامهای کنترلی مختلف دارای خروجی متفاوت میباشد. این امر با عدم وجود هیچ وضعیتی در بخش تعداد وضعیت Home جدول شماره 2 تایید میگردد (هدف 3).
شبکههای پتری رنگی در کنار ارائه امکانات مناسب برای بررسی فرمال در فرآیند مدلسازی قابلیت ارزیابی پارامترهای کمی را نیز به خوبی فراهم ساخته است. بررسی این موارد با مشاهده مقادیر نشانههای تعریف شده پس از اجرای مدل ممکن میگردد. به عنوان مثال در مدل مربوط به پروتکل RPL مقدار انرژی باتری در هر گره میتواند جهت بررسی مصرف انرژی مورد استفاده قرار گیرد. در نمودارهای شماره 11، 12 و 13 به ترتیب میزان مصرف انرژی گرهها (گرههای گراف شکل شماره 10)، میزان ترافیک دریافت شده در ریشه و تعداد پیامهای کنترلی ارسالی با بررسی مقادیر نشانهها آورده شدهاند. لازم به ذکر است که در این بررسی تداخل رادیویی نیز در نظر گرفته شده است.
شکل 11 : مصرف انرژی گرههای درخت شکل شماره 10
شکل 12 : ترافیک دریافت شده در گره ریشه بر اساس گره
شکل 13 : سربار پیامهای کنترلی
همانطور که در نمودار شماره 11 مشاهده میشود میزان مصرف انرژی در پروتکل RPL با توجه به ظرفیت باتریهای امروزی مناسب بوده و قابلیت اجرایی قابل قبولی را دارد. با توجه به نمودار شماره 12 نیز پروتکل RPL میتواند توازن مناسبی را بین گرههای درخت از نظر تعداد پیامهای دریافتی در ریشه ایجاد کند. سربار ناشی از پیامهای کنترلی نیز بر اساس نمودار 13 یک روند کاهشی را دنبال کرده است. امری که نشاندهنده حرکت RPL به سمت ایجاد پایداری در شبکه میباشد.
6- نتیجه گیری
در این مقاله ضمن ارائه یک مدل ماژولار با خوانایی مناسب برای پروتکل مسیریابی RPL به ارزیابی برخی معیارها در ساختار آن با کمک قابلیتهای موجود در شبکههای پتری رنگی پرداخته شد. نتایج حاصل از این بررسی در لیست زیر آورده شده است.
1- شرایط توقف در اجرای پروتکل RPL وجود ندارد. به عبارت دیگر امکان وقوع بنبست در فرآیند مسیریابی ممکن نیست.
2- در پروتکل RPL امکان رخداد حلقه وجود ندارد.
3- مقادیر ورودی در عملکرد این پروتکل موثر است و پروتکل به یک وضعیت خاص هدایت نمیگردد (رفتار متفاوت در مقابل ورودیهای متفاوت).
علاوه بر بررسی ساختاری پروتکل RPL برخی پارامترهای مهم در ارزیابی عملکردی آن نیز به کمک مقادیر نشانهها در شبکههای پتری رنگی مورد بررسی قرار گرفت. نتایج حاصل از این بررسی ضمن نمایش توانایی شبکههای پتری رنگی در بررسی متغیرها، عملکرد مناسب RPL را در مصرف انرژی، ترافیک دریافتی و سربار کنترلی تایید میکند.
لازم به ذکر است که شبکههای پتری رنگی به علت وجود قابلیتهای کارآمدی از جمله پوشش گسستگی، پوشش اتفاقات همزمان و قابلیت مدلسازی ماژولار میتواند یک مدلسازی مناسبی را برای پروتکلهای مسیریابی که ماهیت گسسته و همزمان دارند ارائه دهد. بر این اساس پژوهش جاری میتواند برای محققان بسیاری مفید باشد.
مراجع
[1] K. Gulati, R. S. Kumar Boddu, D. Kapila, S. L. Bangare, N. Chandnani, and G. Saravanan, “A review paper on wireless sensor network techniques in Internet of Things (IoT).” Materials Today: Proceedings, vol. 51, pp. 161-165, 2022, doi: 10.1016/j.matpr.2021.05.067.
[2] A. E. Omolara, “The internet of things security: A survey encompassing unexplored areas and new insights.” Computers & Security, vol. 112, p. 102494, 2022, doi: 10.1016/j.cose.2021.102494.
[3] H. Lamaazi and N. Benamar, “A comprehensive survey on enhancements and limitations of the RPL protocol: A focus on the objective function.” Ad Hoc Networks, vol. 96, p. 102001, 2020, doi: 10.1016/j.adhoc.2019.102001.
[4] R. A. Alexander, J. Brandt, J. Hui, K. Pister, P. Thubert, and T. Winter, RPL: IPv6 Routing Protocol for Low-Power and Lossy Networks (RFC 6550). 2012.
[5] A. Idrees and A. J. Witwit, “ Energy-efficient load-balanced RPL routing protocol for internet of things networks.” International Journal of Internet Technology and Secured Transactions, vol. 11, no. 3, pp. 286-306, 2021.
[6] P. O. Kamgueu, E. Nataf, and T. D. Ndie, “Survey on RPL enhancements: A focus on topology, security and mobility.” Computer Communications, vol. 120, pp. 10-21, 2018, doi: 10.1016/j.comcom.2018.02.011.
[7] K. Jensen and L. M. Kristensen, Coloured Petri Nets. Springer Science & Business Media, 2009.
[8] D. A. Zaitsev and T. R. Shmeleva, “Modeling With Colored Petri Nets.” Automated Systems in the Aviation and Aerospace Industries, pp. 378-404, 2019, doi: 10.4018/978-1-5225-7709-6.ch014.
[9] Y. Chen, K. Hou, J. Chanet, and K. GHOLAMI, “A RPL based Adaptive and Scalable Data-collection Protocol module for NS-3 simulation platform.” NICST 2103 New Information Communication Science and Technology for Sustainable Development: France-China International Workshop, 2013.
[10] L. Bartolozzi, T. Pecorella, and R. Fantacci, “ns-3 RPL module: IPv6 Routing Protocol for Low power and Lossy Networks.” Proceedings of the Fifth International Conference on Simulation Tools and Techniques, 2012, doi: 10.4108/icst.simutools.2012.247718.
[11] P. Karkazis, P. Trakadas, T. Zahariadis, A. Hatziefremidis, and H. C. Leligou, “RPL modeling in J-Sim platform.” 2012 Ninth International Conference on Networked Sensing (INSS), 2012, doi: 10.1109/inss.2012.6240559.
[12] J. Tripathi, J. C. De Olive, and J. P. Vasseur, “A performance evaluation study of RPL: Routing Protocol for Low power and Lossy Networks.” 2010 44th Annual Conference on Information Sciences and Systems (CISS), 2010, doi: 10.1109/ciss.2010.5464820.
[13] M. Becker, K. Kuladinithi, and C. Görg, “Modelling and Simulating the Trickle Algorithm.” Lecture Notes of the Institute for Computer Sciences, Social Informatics and Telecommunications Engineering, pp. 135-144, 2012, doi: 10.1007/978-3-642-30422-4_10.
[14] L. M. Kristensen and V. Veiset, “Transforming CPN Models into Code for TinyOS: A Case Study of the RPL Protocol.” Application and Theory of Petri Nets and Concurrency, pp. 135-154, 2016, doi: 10.1007/978-3-319-39086-4_10.
[15] L. Wallgren, S. Raza, and T. Voigt, “Routing Attacks and Countermeasures in the RPL-Based Internet of Things.” International Journal of Distributed Sensor Networks, vol. 9, no. 8, p. 794326, 2013, doi: 10.1155/2013/794326.
[16] W. Yu, M. Jia, X. Fang, Y. Lu, and J. Xu, “Modeling and analysis of medical resource allocation based on Timed Colored Petri net.” Future Generation Computer Systems, vol. 111, pp. 368-374, 2020, doi: 10.1016/j.future.2020.05.010.
[17] A. Shahidinejad, M. Ghobaei-Arani, and L. Esmaeili, “An elastic controller using Colored Petri Nets in cloud computing environment.” Cluster Computing, vol. 23, no. 2, pp. 1045-1071, 2019, doi: 10.1007/s10586-019-02972-8.
[18] G. Cavone, M. Dotoli, and C. Seatzu, “A Survey on Petri Net Models for Freight Logistics and Transportation Systems.” IEEE Transactions on Intelligent Transportation Systems, vol. 19, no. 6, pp. 1795-1813, 2018, doi: 10.1109/tits.2017.2737788.
[19] G. P. Bhandari and Ratneshwer, “Dependency-based fault diagnosis approach for SOA-based systems using Colored Petri Nets.” Journal of King Saud University - Computer and Information Sciences, vol. 34, no. 2, pp. 480-491, 2022, doi: 10.1016/j.jksuci.2018.12.002.
[20] H. Kaid, A. Al-Ahmari, Z. Li, and R. Davidrajuh, “Single Controller-Based Colored Petri Nets for Deadlock Control in Automated Manufacturing Systems.” Processes, vol. 8, no. 1, p. 21, 2019, doi: 10.3390/pr8010021.
[21] M. Pishdar, Y. Seifi, M. Nasiri, and M. Bag-Mohammadi, “PCC-RPL: An efficient trust-based security extension for RPL.” Information Security Journal: A Global Perspective, vol. 31, no. 2, pp. 168-178, 2021, doi: 10.1080/19393555.2021.1887413.
[22] A. Kamble, V. S. Malemath, and D. Patil, “Security attacks and secure routing protocols in RPL-based internet of things: Survey,” 2017 International Conference on Emerging Trends & Innovation in ICT (ICEI), 2017.
[23] V. Adat and B. B. Gupta, “Security in Internet of Things: issues, challenges, taxonomy, and architecture.” Telecommunication Systems, vol. 67, no. 3, pp. 423-441, 2017, doi: 10.1007/s11235-017-0345-9.
[24] O. Iova, P. Picco, T. Istomin, and C. Kiraly, “RPL: The Routing Standard for the Internet of Things.. Or Is It?” IEEE Communications Magazine, vol. 54, no. 12, pp. 16-22, 2016, doi: 10.1109/mcom.2016.1600397cm.