بخشی از مقاله
چکیده:
در اینترنت اشیاء، مساله یافتپذیری اشیاء هوشمند و خدماتی که ارائه میدهند باید به گونهای حل شود که این اشیاء قابل جستجو و قابل یافت شدن باشند. برای آنکه اطلاعات ساختاری IOT توسط ماشین ها قابل پردازش و برخی عملیات های مرسوم بر روی این اطلاعات قابل انجام باشد، می توان آنها را در چارچوب مدل داده ایی RDF که یک مدل مبتنی بر گراف است ذخیره نمود. برای یافتن اطلاعات مورد نیاز بر روی ساختمان داده گراف روشهای جستجوی گوناگونی وجود دارد. در این تحقیق با تلفیق اتوماتای یادگیرنده توزیع شده با الگوریتم جستجوی قدم زدن تصادفی روشی هوشمند برای بهینه نمودن جستجو بر روی یک گراف RDF ارائه شده است.
اتوماتای یادگیرنده تعداد محدودی اقدام قابل انتخاب دارد که پس از انتخاب یک اقدام، بازخورد دریافتی از محیط که ناشی از این اقدام بوده است را ذخیره می نماید تا بتواند در مراحل بعدی اقدامات هوشمندانه تری انجام دهد. الگوریتم پیشنهادی پیاده سازی و کارایی آن بر روی یک گراف معنایی با 100 نود مورد ارزیابی قرار گرفته است. نتایج این ارزیابی نسبت به روش پایه که تنها از قدم زدن تصادفی برای جستجو استفاده نموده بهبود یافته است.
کلمات کلیدی: اینترنت اشیاء , اتوماتای یادگیر , قدم های تصادفی
-1 مقدمه
در سالهای اخیر، قیمت ارزان سنسورها و پیادهسازی آسان شبکههای حسگر بیسیم، توسعه تکنیکهای ارتباطی و ظهور اشیاء هوشمند گوناگون، منجر به افزایش روزشمار تعداد اشیاء فیزیکی متصل به هم شدهاست؛ به طوریکه شرکت سیسکو تعداد دستگاههای متصل به هم را تا سال 2020 در حدود 50 میلیارد عدد پیشبینی کردهاست .[1] ناهمگونی دستگاهها و ساختار دادههایی که تولید میکنند و موقعیتهای جغرافیایی متفاوت اشیاء، موانعی بر سر راه توسعه اپلیکیشنهای - کاربردهای - جدید در IOT است؛ که این مساله نیازمند گردآوری دادهها از چندین منبع و ترکیب آنها با یکدیگر به منظور تشخیص الگو و کشف اطلاعات ارزشمند میباشد.
هر چند دسترسی به میلیونها دستگاه هوشمند از طریق شبکه اینترنت به یکدیگر، محیط جذابی برای انواع کاربردها فراهم آورده و مزایای گوناگونی خواهد داشت؛ اما این مساله چالشهای زیادی را نیز به همراه دارد که از آن جمله میتوان به جستجو و یافتن خدمات درخور اشاره نمود: در میان یک اکوسیستم، از میان میلیاردها شئ هوشمند چگونه میتوانیم خدمات مورد نظرمان رابیابیم تا بتوانیم با یکپارچهسازی این خدمات، کاربرد مورد نظرمان را ارائه دهیم؟ [2] دنیای وب نیز در هنگام گذر از مرحله هزاران صفحه گسترده به
مرحله افزوده شدن حجم بیشماری از محتوای چندرسانهای و سرویسهای گوناگون، با چالشهای مشابهای روبرو بود. همانطور که موتورهای جستجو در وب ظاهر شدند تا خدمات جستجو و ایندکس گذاری را ارائه دهند، در اینترنت اشیاء، مساله یافتپذیری اشیاء هوشمند و خدماتی که ارائه می دهند باید به گونهای حل شود که این اشیاء قابل جستجو و قابل یافت شدن باشند .[2] جستجوی اشیا وخدمات پیچیدگی بسیار بیشتری نسبت به جستجوی اسناد در وب دارد چرا که آنها به شدت به اطلاعات محیطی مانند موقعیت مکانی درآمیخته اند و اغلب از یک محیط به محیط دیگر در حرکتند و نیز هیچگونه ویژگی که بسادگی قابل ایندکس شدن باشد ندارند - در وب یک سند متنی قابل خواندن براحتی قابل ایندکس شدن است - .[3]
اشیا هوشمند نیازمند مکانیسمی هستند تا بتوانند خودشان و خدماتشان را برای دیگران - انسانها و سایر دستگاهها - معرفی نمایند تا بطور اتوماتیک قابل کشف و استفاده باشند؛ برای حل این مساله زبان هایی طراحی شده اند که هم برای انسان و هم برای ماشین قابل فهم هستند مانند: RDF و Microformats .زبان توصیفی RDF یا چارچوب توصیف منابع نوعی مدل داده ای است که برای ذخیره و بازیابی معنای قابل پردازش توسط ماشین بکار می رود. همچنین RDF مدلی است مبتنی بر گراف که از آن به منظور توصیف منابع اینترنتی و نیز چگونگی ارتباط این منابع با یکدیگر به عمل می آید.
از روش های جست و جو می توان به جست و جو با استفاده از تکنیک قدم های تصادفی اشاره کرد. قدم های تصادفی یک فرآیند تصادفی است که متشکل از مجموع یک دنباله از تغییرات در یک متغیر تصادفی است. این تغییرات با تغییرات گذشته، به معنی این است که هیچ الگویی برای تغییرات در متغیر تصادفی وجود ندارد و این تغییرات قابل پیش بینی نیست. قدم های تصادفی برای تعیین محل احتمالی یک "پیاده رونده" در یک حرکت تصادفی، که در آن محل قرار دارد از مجموع دنباله ای از تغییرات استفاده می کند. الگوریتم -K قدم های تصادفی، نمونه ای از روش های جستجوی کورکورانه در شبکه های نظیر به نظیر غیر ساخت یافته هستند. زمانی که در گرافی قرار داریم با توجه به اینکه در حالت های مختلف می توان حرکت کرد باید به صورت تصادفی یکی از حالت ها را انتخاب کرد.
در وب اشیا نیز هدف ما این است که، زمانی که مجموعه ای ازگراف RDF را داریم و می خواهیم یک شی یا خدمتی را در گراف RDF جستجو کنیم، شروع به ویزیت کردن گره ها نموده و باید بهترین گره ای که با مورد جستجوی مان همخوانی دارد را پیدا کنیم. وقتی جستجوی یک شی ناموفق باشد، K گره از بین همسایه ها به طور تصادفی، انتخاب می شوند و درخواست ها به سمت آنها هدایت می شوند. زمانی جستجو موفقیت آمیز خواهد بود که یک شیء توسط حداقل یکی از همسایه ها پیدا شود. با به کار بردن روش های یادگیری در شبکه، هر گره می تواند وضعیت شبکه را یاد بگیرد و برای مراحل بعدی جست و جو، براساس بازخورد دریافتی از گره ها تصمیم گیری کند. انتظار می رود در رویکردهای جست و جوی مبتنی بر یادگیری، زمان پاسخ کوتاهتر، بار شبکه کمتر و میزان مصرف پهنای باند بهبود یابد.
اتوماتای یادگیر ماشینی است که می تواند تعدادی متناهی عمل را انجام دهد. هر عمل انتخاب شده توسط یک محیط احتمالی ارزیابی شده و نتیجه ارزیابی در قالب سیگنالی مثبت یا منفی به اتوماتا داده می شود و اتوماتا از این پاسخ در انتخاب عمل بعدی تاثیر می گیرد. هدف نهایی آن است که اتوماتا یاد بگیردکه از بین اعمال خود بهترین عمل را انتخاب کند. بهترین عمل، عملی است که احتمال دریافت پاداش از محیط را به حداکثر برساند و بدترین عمل، عملی است که احتمال دریافت جریمه را خواهد داشت.
هدف ما این است که زمانی که می خواهیم در گراف متناظر با اشیا به هم متصل جستجو نموده و حرکت کنیم، متناسب با هر گره گراف یک اتوماتای یادگیر در نظر می گیریم، که عمل های آن انتخاب هرکدام از یال هاست که در قدم های تصادفی هم باید یکی از این یال ها را انتخاب کنیم و در واقع داریم این 2 روش را با هم ترکیب می کنیم. یعنی می خواهیم با قدم های تصادفی حرکت را شروع کنیم و براساس اتوماتای یادگیر حرکت را ادامه دهیم تا به هدف برسیم که در این روش براساس یک احتمال یکی از یال ها را انتخاب می کند - احتمال اولیه همه یال ها را یکسان در نظر می گیریم - و با توجه به اینکه به جواب مورد نظر رسیده یا خیر احتمال آن را بالا یا پایین می آورد یعنی پاداش یا جریمه دریافت می کند بدین ترتیب بهترین مسیر انتخاب می شود و می توان در یک فرآیند تکراری به بهترین جواب رسید و بهترین نتیجه جستجو را ارائه دهد.
-2 کارهای مرتبط
محمد رفیع خوارزمی الگوریتم های جدیدی براساس اتوماتای یادگیر برای یافتن پارامترهای ویولت ارائه کرده است. در این روش از قدرت تصمیم گیری و جستجوی اتوماتای یادگیر استفاده کرده و در هر مرحله با اضافه کردن ویولت جدید به تقریب قبلی و حذف ویولتهایی که به کاهش خطا کمکی نمی کنند سعی در کاهش خطا می نماید.یکی از مزیت های این روش تعیین تعداد توابع پایه می باشد زیرا تعداد توابع پایه از قبل مشخص نمی باشند بلکه همزمان با فرایند تقریب مشخص می شود.[14] رضا رستگار یک الگوریتم تکاملی جدیدی از دسته الگوریتم های تخمین توزیع با استفاده از اتوماتای یادگیر معرفی شده نموده است. در این الگوریتم با فرض استقلال متغیرهای مسئله بهینه سازی، از اتوماتای یادگیر برای تخمین توزیع احتمالاتی متغیرها استفاده شده است.[15]
Neeraj Kumar و et مسیریابی مشترک اتوماتای یادگیر مبتنی بر نجات در انبوه مناطق شهری با استفاده از شبکه های حسگر فضایی بیان شده. در این مقاله، پیشنهاد شده است الگوریتم مبتنی بر مسیریابی اتوماتای یادگیر را برای ارسال اطلاعات به مقصد مورد نظر با حداقل تاخیر و حداکثر توان. اتوماتا یادگیری - LA - مستقر در نزدیکترین نقاط دسترسی - APS - با تجربه گذشته خود در شبکه بودن را یاد بگیرند و برای مسیریابی به سرعت تصمیم گیری کنند. استراتژی پیشنهادی متشکل از تقسیم کل منطقه به دسته های مختلف، که بر اساس آن یک مسیر بهینه سازی شده با استفاده از LA داشتن پارامترهای ورودی مشترک به عنوان چگالی خودرو انتخاب شده است،فاصله از نزدیکترین واحد خدمات، و تاخیر.یک عبارت نظری برای برآورد چگالی مشتق شده است،که برای انتخاب "بهترین" مسیر با LA استفاده می شود. [7]
آگاه از متن - بافت - به نام CASSARAM برای اینترنت اشیاء ارائه نمودهاند. هدف از این مدل فائق آمدن بر چالشهای جستجو و انتخاب سنسورها در محیطی که تعداد زیادی از سنسورها با همپوشانی و گاه افزونگی در وظایف وجود دارند. CASSARAM جستجو و انتخاب سنسورها بر اساس اولویتهای کاربر انجام میدهد. در این روش، مشخصههایی از سنسور، مانند دقت، طول، عمر باطری، قابلیت اعتماد و ... در نظر گرفته میشوند. در آن هم از جستجوی معنایی و هم از تکنیکهای استدلال کمی بهره گرفته شدهاست. ایندکس گذاری و رتبهبندی سنسورها با تکنیک مقایسه فاصله اقلیدسی وزندار در فضای چندبعدی بر اساس اولویتهای کاربران صورت میگیرد.
هدف این روش، نشان دادن اهمیت جستجوی سنسورها در اینترنت اشیاء، مشخص نمودن ویژگیهایی از سنسورها و نیز فرآیند اکتساب داده که به انتخاب سنسورها کمک میکند و فهم چگونگی کمک نمودن استدلال معنایی و آماری در ترکیب با یکدیگر به چالش جستجو و انتخاب سنسورها بیان شده است. فقیه و همکاران در [5] یک موتور جستجوگر موضوعی برای اینترنت اشیاء پیشنهاد دادهاند. انگیزه این کار، کارایی نسبتا پایین موتورهای جستجوی همهمنظوره که به نتایج خزندههای عمومی وب بستگی دارند، میباشد. موتور جستجوگر موضوعی، سیستمی است که از نمونهها، تخصصیسازی را یاد گرفته و سپس با راهنمایی یک مکانیسم رتبه دهی، بر اساس محبوبیت و مرتبط بودن به کاوش وب میپردازد.
عملکرد این موتور جستجوی موضوعی بدین صورت است که در ابتدا یک برنامه خزنده وب به جستجوی صفحاتی از وب میپردازد که محتوای آنها مرتبط با اینترنت اشیاء است؛ این امر توسط چندین برنامه خزنده و به صورت توزیعشده محقق میشود. صفحات گردآوری شده به واژههای کلیدیشان تجزیه میشوند، سپس URLهای این صفحات ایندکس شده و در یک پایگاه داده با توجه به واژههای کلیدیشان ذخیره میشوند. وقتی که یک پرسوجو از سمت یک کاربر میرسد؛ جستجو در این پایگاه داده انجام میشود و نتیجه مناسب به کاربر ارائه میشود.
نتایج حاصل از این موتور جستجوی موضوعی بدین صورت میباشد:
ابراهیمی و همکاران در[6] با الهام گرفتن از الگوریتم خوشهبندی مورچهها یک روش آگاه از متن - بافت - برای خوشهبندی سنسورها به شکل یک شبکهای معنایی از سنسورها که در آن سنسورهای با اطلاعات محیطی یکسان در یک خوشه جمع میشوند، ارائه دادهاند. در این روش، در ابتدا سنسورها بر اساس نوعشان گروهبندی میشوند؛ سپس یک الگوریتم فراهیوریستیک به نام AntClust بهکار گرفته میشود تا سنسورها را بر اساس اطلاعات محیطیشان خوشهبندی نماید. در نهایت کمی تنظیمات سودمند برای کاهش هزینه جستجو صورت میگیرد. در نتیجه این اقدامات، جستجوی یک کاربر تنها به سمت خوشهای مناسب هدایت میشود که کاهش چشمگیری در فضای جستجوی سنسورها را در پی خواهد داشت.
