طراحی و بهبود یک الگوریتم­ یادگیرنده برای جستجوی منابع در شبکه نظیربه­ نظیر بر روی شبکه ادهاک سیار

نویسندگان

1 دانشگاه آزاد اسلامی واحد قزوین، دانشکده مهندسی کامپیوتر و فناوری اطلاعات، قزوین، ایران،

2 استاد، دانشکده مهندسی برق دانشگاه صنعتی امیر کبیر، تهران، ایران

چکیده

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

کلیدواژه‌ها


[1]          Huang,W.,  Nahrstedt, K., Wu, B., Message propagation in adhoc based proximity mobile social networks, In Proceeding 8th IEEE International Conference on Pervasive Computing and Communications Workshops(PERCOM Workshops), 2010, 114-146.

[2]          Tsai,F., Han, W., Xu, J., Chua, H., Design and development of a mobile peer-to-peer social networking application, Journal Elsevier of Expert System and Appllication, vol. 36, 2009, 11077–11087.

[3]          Borg J., A, comparative study of ad hoc & peer to peer networks, Master’s thesis, University College London, 2003.

[4]          Ding G., Bhargava B., Peer-to-peer file-sharing over mobile ad hoc networks, In Proceeding 2th IEEE Annual Conference on Pervasive Computing and Communications Workshops, 2004, 104-108.

[5]          Franciscani F.P., Vasconcelos M. A, et al, Peer-to-peer over ad-hoc networks configuration algorithms, In proceedings 17th IEEE International Parallel and Distributed Processing Symposium, 2003.

[6]          Hu Y. C, Das S. M, Pucha H., Exploiting the Synergy between Peer-to-Peer and Mobile Ad Hoc Networks, In Proceeding HotOS-IX: Ninth Workshop on Hot Topics in Operating Systems, Vol. 9, 2003, 7-7.

[7]          Xu, B., Wolfson, O., Data Management in Mobile Peer-to-Peer Networks, In Proceeding of Databases, Information Systems and Peer-to-Peer Computing (DBISP2P), 2004, 1-15.

[8]          Huang, Z., Jensen,C., Lu, H., Ooi,B., Skyline Queries Against Mobile Lightweight Devices in MANETs, In Proceeding of International Conference on Data Engineering (ICDE), 2006, 66-74.

[9]          Shirky,C., What Is P2P And What Isn’t,” OpenP2P.com, 2000.

[10]        Chu, J., Labonte, K., Levine, B., Availability and locality measurements of peer-to-peer file systems .In Proceeding of ITCom: Scalability and Traffic Control in IP Networks SPIE, 2002.

[11]        Tung, Y., Lin, K., Location-Assisted Energy-Efficient Content Search for Mobile Peer-to-Peer Networks, In Procedding 7th International Workshop on Mobile Peer-to-Peer Computing IEEE, 2011, 477-482.

[12]        Kalogeraki, V., Gunopulos, D., Zeinalipour-Yazti, D., A Local Search Mechanism for Peer-to-Peer Networks, In Proceeding of 11th international conference on Information and knowledge management CIKM, 2002, 300-307.

[13]        http://www.gnutella.com, Gnutella website.

[14]        Gkantsidis, C., Mihail, M., Saberi, A., Random Walks in Peer-to-Peer Networks, In Proceeding INFOCOM  Twenty-third AnnualJoint Conference of the IEEE Computer and Communications Societies , Vol 1, 2004, 1-12.

[15]        Hora, D., Macedo, D.F., Oliveira, L. B., and et al. Enhancing peer-to-peer content discovery techniques over mobile ad hoc networks, Journal of Elsevier Computer communication, Vol.32, 2009, pp 1445-1459.

[16]        Cao, H., Wolfson, O., Xu, B., Yin, H., (2005), MOBI-DIC: MOBIle Discovery of local Resource in Peer-to-Peer Wireless Network, In Proceeding IEEE Computer Society Technical Committee Data Engineering, 232-240.

[17]        Lv, Q., Cao, P., Cohen, E., Li, K., Shenker, S., Search and replication in unstructured peer-to-peer network, In Proceeding of the 16th ACM International Conference on Supercomputing (ICS’02), ACM, 2002, 329–350.

[18]        Tsoumakos, D., Roussopoulos, N., Adaptive Probabilistic (APS) for Peer-to-Peer Networks, In Proceesings of Peer-to-Peer computing, 2003, 102-109.

[19]        Tsoumakos, D., Roussopoulos,N., Evaluation of ad hoc routing protocols under a peer-to-peer application, In Proceeding of the 3rd  International Conference on Peer-to-Peer Computing )P2P), 2003, 102–109.

[20]        Tsoumakos, D., Roussopoulos, N., Adaptive Probabilistic (APS) for Peer-to-Peer Networks, In Proceedings of the 3rd international conference on peer-to-peer computing, 2003, 102-109.

[21]        Shojafar, M., Abawajy, J., Delkhah, Z., Pooranian, Z., Abraham, A., An efficient and distributed file search in unstructured peer-to-peer networks, Journal of Peer-to-peer Network Application, Springer Journal, pp. 356-362, 2013.

[22]        Demers, A., Greene, D., Hauser, C., Irish, W., Larson, J., Shenker, S., Sturgis, H., Swinehart, D., Terry, D., (1987), Epidemic algorithms for replicated database maintenance, In Proceedings of the Sixth Annual ACM Symposium on Principles of Distributed Computing (PODC), 1–12.

[23]        Eugster, P.T., Guerraoui, R., Kermarrec, A.M., Massoulié, L., (2004),From epidemics to distributed computing, In Proceeding IEEE Computer, Vol. 37, No. 5, 60–67.

[24]        Jelasity, M., Babaoglu, O., Man, T., (2009), Gossip-based fast overlay topology construction, Computer Networks, Vol. 53, No. 13, 2321–2339.

[25]        Kermarrec, A.M., Massoulié, L., Ganesh, A.J., (2003), Probabilistic reliable dissemination in large-scale systems, In Proceeding IEEE Transactions on Parallel and Distributed systems, 248–258.

[26]        Jelasity, M., Montresor, A., Babaoglu, O., (2005), Gossip-based aggregation in large dynamic networks, ACM Transactions on Computer Systems (TOCS), Vol. 23, No. 3, 245 -252.

[27]        Renesse, R. V., Minsky, Y., Hayden, M., (1998), A gossip-style failure detection service, In Proceedings of Middleware’98, IFIP International Conference on Distributed Systems Platforms and Open Distributed Processing, 55–70.

[28]        Pouwelse, J.A., Garbacki, P., Wang, J., Bakker, A., Yang, J., Iosup, A., Epema, D.H., Reinders, M., Van Steen, M.R., Sips, H.J., (2008), Tribler: a social-based peer-to-peer system, Concurrency and Computation, Vol. 20, No. 2, 120-127.

[29]        Zhang, X., Liu, J., Li, B., Yum, T.S.P., (2005), Cool Streaming/DONet: a data-driven overlay network for efficient live media streaming, In Proceedings of IEEE Infocom, No. 3, 13–17.

[30]        Haas, Z.J., Halpern, J.Y., Li, L., (2006), Gossip-based ad hoc routing, In Proceeding IEEE/ACM Transactions on Networking  (TON), Vol. 14, No. 3, 485-491.

[31]        Hayashi, H., Hara, T., Nishio., S., (2003), Cache invalidation for updated data in ad hoc net-works, In Proceeding International Conference on Cooperative Information Systems (CoopIS'03), Vol. 2888, 516-535.

[32]        Verma, S., Ooi, W., (2005), Controlling Gossip Protocol Infection Pattern Using Adaptive Fanout, In Proceeding 25th IEEE International Conference on Distributed Computing Systems, 665 – 674.

[33]        Wolfson, O., Xu, B., Yin, H., Cao, H, (2006), Search-and-Discover in Mobile P2P Network Databases, In Proceedings of the 26th IEEE International Conference on Distributed Computing Systems (ICDCS'06), 65-70.

[34]        Papadopouli, M., Schulzrinne, H., (2001), Effects of power conservation, wireless coverage and cooperation on data dissemination among mobile devices, In Proceeding MobiHoc '01 of the 2nd ACM international symposium on Mobile ad hoc networking & computing, 117-127.

[35]        Gao, G., Li, R., He, H., Xu, Z., Distributed cashing in structured peer-to-peer file sharing networks, Computer and Electrical Engineering, Elsevier Journal, Vol. 40, 2013, 688-703.

[36]        Luo X, Qin Z, Geng J, Luo J. IAC: Interest-aware caching for unstructured P2P, in SKG, IEEE Computer Society, 2006, 58.

[37]        Najim, K., Poznyak, A.S., Learning automata:  theory and application, in proceeding of the Tarrytown, New York, Elsevier Science Publishing Ltd., 1994.

[38]        M.Kumpati, Thathachar and Narendra, Learning Automata-A Survey, In Proceeding of IEEE Transactions on systems, Man and Cybernetics, 1974.

[39]        Babaei, H., Fathy, M., Berangi, R., The impact of mobility models on the performance of P2P content discovery protocols over mobile ad hoc networks, Journal of Springer, vol 6, 2012, 344-348.

[40]        Cisco aironet 350 series client adapters. Available from: http://www.cisco.com/en/US/prod/collateral/wireless/ps6442/ps4555/ps581product_data_sheet09186a00801ebc29.html, 2008