1.   مشاوره و انجام پروپوزال  و پایان نامه ، مشاوره در زمینه ارائه سمینار، 
       مشاوره و انجام مقاله های بین المللی و داخلی، 
       مشاوره و انجام مقاله در مجله های علمی پژوهشی معتبر، 
        مشاوره و آموزش شبیه سازی شبکه توسط شبیه ساز آکادمیک 2-NS، 
         مشاوره و آموزش شبیه سازهای ترافیک شهری از قبیل  SUMO، ONE، و ...
          کمک به دانشجویان برای پیاده سازی ایده ها و مقالات خود با شبیه سازهای
               NS2, NS3 , OMNET++ , ONE
     
    
                 شماره تماس :
                         حسین رنجبران:    09101607834   
                                          
    
                  ساعات تماس: 
                                      ۸ الی ۲۰
                         
                   ایمیل:
                         hossein.ranjbaran.it@gmail.com
                        
           
    

دسته بندی مسائل پوشش در شبکه های حسگر

شروع موضوع توسط AdMiN ‏23/1/14 در انجمن پوشش و پروتکلهای پوشش

وضعیت موضوع:
You must be a logged-in, registered member of this site to view further posts in this thread.
  1. AdMiN

    AdMiN Administrator هیات مدیره

    ما به طور كلي برروي مسئله پوشش در شبكه هاي حسگرايستاکار مي كنيم بدين معنا كه فرض براين است که از وقتي كه نودهاي حسگر در محيط مستقر مي شوند حركت نمي كنند وجايشان ثابت است. در ضمن منطقه حسگري، ديسكي است به مركزيت حسگر وشعاع برد حسگري ومنطقه ارتباطي هر حسگر، ديسكي است به مركزيت حسگر وشعاع برد ارتباطي حسگر. بيشتر مسائلي كه دراين زمينه مطرح شده اند بدين صورت دسته بندي مي گردند. پوشش ناحيه اي، پوشش نقطه اي وپوشش مرزي كه در ادامه مورد بحث قرار مي گيرند:

    پوشش ناحيه اي

    بيشتر مسائل مطالعه شده در زمينه پوشش، مسائل پوشش ناحيه اي هستند كه دراين مسائل هدف اصلي شبكه حسگر اين است كه يك ناحيه يا يك منطقه را تحت پوشش حسگري حسگرهايش قرار دهد.

    شکل 1 مثالي از توزيع تصادفي حسگرها جهت پوشش يك ناحيه مربع شكل را نشان مي دهد. همان گونه كه مشاهده مي كنيد اگر فقط نودهاي به رنگ سياه فعال بمانند. كل ناحيه را پوشش مي دهند. وبقيه نودها مي توانند غير فعال گردند. هدف اصلي مسئله پوشش ناحيه اي شبكه حسگر اين است كه شبكه، محيط را به گونه اي پوشش دهد كه مصرف انرژي حسگرهاي شبكه به صورت كارا باشد. مصرف كاراي انرژي يكي از دغدغه هاي اصلي در شبكه هاي حسگر بي سيم است كه داراي منابع انرژي محدودند. مكانيزم هايي كه از مصرف زياد انرژي در شبكه هاي حسگر جلوگيري مي كنند، باعث افزايش طول عمر شبكه مي شوند. طول عمر شبكه به طور كلي فاصله زماني در نظر گرفته مي شود كه شبكه مي تواند عمليات حسگري وانتقال داده ها به ايستگاه پايه را انجام دهد. در طول حيات شبكه بعضي از نودها ممكن است از بين بروند (به دليل خرابيهاي فيزيكي يا تخليه منبع انرژي ) يا نودهاي اضافي در شبكه استقرار يابند. مكانيزم موثري كه اغلب مورد استفاده قرار مي گيرد، زمانبندي فعاليت نودهاي حسگر وقرار دادن نودهاي اضافي درحالت غير فعال تا زمان ممكن، مي باشد ، جهت طراحي چنين مكانيزمي ما بايد به سوالات زير پاسخ دهيم :

    · نود بر اساس چه قواعدي بايد لزوم فعال يا غير فعال شدن خود را تشخيص دهد؟

    · در چه زماني نودها بايد چنين تصميمي بگيرند؟

    چه مدت بايد يك نود درحالت غير فعال بماند؟

    upload_2014-1-23_15-14-34.png
    شکل‏1: پوشش ناحيه ای


    در ادامه به تعدادي ازمكانيزمهايي كه بدين منظور مورد استفاده قرار گرفته اند اشاره مي شود: در كارهاي [1] و[2] جمعيت زيادي از حسگرها، به صورت تصادفي جهت مشاهده محيط استقرار مي يابند وهدف اين است كه به يك طراحي با مصرف انرژي به صورت كارا كه پوشش شبكه را نيز حفظ مي كند برسيم. از آنجاييكه تعداد نودهاي مستقر در محيط بيش از تعداد مورد نياز جهت مشاهده محيط در حالت بهينه است، راه حل پيشنهادي اين است كه نودها به مجموعه هاي متصل تقسيم گردند. وزماني كه يك مجموعه از حسگرها فعالند، بقيه حسگرها بايد درحالت غير فعال قرار گيرند. هدف روش اين است كه حداكثر تعداد مجموعه هاي منفصل را بيابد كه اين مطلب مستقيما برروي طول عمر شبكه تاثير مي گذارد. راه حل هاي ارائه شده در اين دو كار به صورت متمركز عمل مي كنند. در [1] محيط به صورت مجموعه اي از ميادين مدل مي گردد به طوري كه نقاط هر ميدان به وسيله مجموعه يكساني از حسگرها تحت پوشش قرار ميگيرند. الگوريتم [1] پوشش هاي منفصل را با انتخاب حسگرهايي كه عنصر بحراني (ميداني كه به وسيله مينيمم تعداد حسگرها پوشش داده مي شود) را پوشش مي دهند وبا اولويت دادن به حسگرهايي كه تعداد ميدان هاي پوشش داده نشده بيشتري را پوشش مي دهند يا ميدان هايي را پوشش مي دهند كه حسگرهاي كمتري آنها را پوشش مي دهند به مسئله پوشش مي پردازد. وحسگرهايي كه ميدان هاي پوشش داده شده را پوشش نمي دهند، به صورت پي در پي محاسبه مي كند. در [2] مجموعه هاي منفصل به صورت مجموعه هاي كنترلي منفصل مدل مي گردند محاسبه ماكزيمم تعداد مجموعه هاي كنترلي منفصل يك مسئله NP-Complete است و براي حل آن الگوريتم رنگ آميزي گراف پيشنهاد شده است. شبيه سازيها نشان داده اند كه مجموعه هاي محاسبه شده بين 5/1 تا 2 برابر بيش از مجموعه هاي بدست آمده توسط الگوريتم [1] بوده است با كمتر از 5 درصد فقدان پوشش شبكه.

    مكانيزم پوشش مبتني بر زمان بندي نود ديگري در [3] پيشنهاد شده است. اين پروتكل به صورت توزيع شده ومحلي عمل مي كند. دراين پروتكل با استفاده از يك قاعده، تشخيص داده مي شود كه آيا ناحيه حسگري نود در ناحيه حسگري همسايگانش قرار مي گيرد ياخير. راه حل تشخيص اينكه آيا پوشش يك نود به وسيله همسايگانش پشتيباني مي گردد، در چندين حالت ارائه گرديده است: زماني كه نودها دامنه حسگري يكسان دارند وموقعيتشان را مي دانند، زماني كه نودها دامنه حسگري يكسان دارندومي توانند اطلاعات جهتي نود همسايه را بدست آورند. وزماني كه نودها دامنه حسگري متفاوتي دارند. شماي زمانبندي نود به دورهايي تقسيم مي گرد به طوري كه هر نود يك فاز زمان بندي دارد وسپس يك فاز حسگري. در فاز زمان بندي نود بايد شايستگي غير فعال شدن را تشخيص دهد. نودهاي انتخاب شده براي غير فعال شدن واحد هاي ارتباطي وحسگري خود راغير فعال مي كنند. درحالي كه بقيه نودها در فازحسگري عمل حسگري را انجام مي دهند. جهت بدست آوردن اطلاعات همسايگان، هر نود در شروع هر دور، يك پيام اعلان موقعيت شامل شماره شناسايي ومكان نود به صورت پخشي ارسال مي نمايد. اگر يك نود وپشتيبانش به طورهمزمان قاعده شايستگي را اجرا نمايند، ممكن است به طور همزمان تصميم به غير فعال شدن بگيرند كه باعث ايجاد نقاط كور در ناحيه مي شود.

    براي اينكه اين مشكل پيش نيايد بدين صورت عمل مي شود كه هر نود ارزيابي را بعد از يك زمان تصادفي شروع مي كند واگر تصميم گرفت كه غير فعال گردد يك پيام به همسايگانش ارسال مي كند وسپس مدت زماني مشخص منتظر مي ماند واگر پيام بروزرساني از همسايگانش دريافت نكرد غير فعال مي گردد. اين تحقيق مكانيزم هاي همزماني رابه صورت تفصيل مشخص نكرده است. اين كار به صورت يك توسعه بر پروتكل خوشه بندي[LEACH [4 پياده سازي شده است ونتايج شبيه سازي افزايش 7/1 برابري در ميانگين زمان حيات سيستم را نشان مي دهد.

    در [5] يك راه حل زمان بندي نود مبتني بر كاوش، براي مسئله پوشش بامصرف كاراي انرژي پيشنهاد شده است. در اينجا حسگرها دامنه حسگري يكساني دارند. قاعده تشخيص شايستگي نود جهت غير فعال شدن براساس يك مكانيزم کاوش طرح ريزي شده است. حسگر يك پيام كاوش PRB با برد R ارسال مي كند. هر نود كه اين پيام را دريافت كند با يك پيام PRB-RPY پاسخ مي دهد. اگر حداقل يك پاسخ دريافت شود، نود به حالت غير فعال مي رود. برد كاوش براساس چگالي مطلوب نود (تعداد نودها به واحد ناحيه) يا براساس افزونگي مطلوب پوشش تعيين مي گردد. درحالي که زمان فعال براساس زمان تناوب حسگري تحمل پذير مشخص مي شود. اين پروتكل، توزيع شده محلي است پيچيدگي آن پايين است اما پوشش ناحيه را به طور كامل تضمين نمي كند.

    در [6] مسئله پوشش به عنوان يك مسئله تصميم گيري مدل شده است، بدين صورت كه يك مجموعه از حسگرها در يك محيط هدف پخش شده اند. مسئله اين است كه تشخيص داده شود كه آيا محيط k-پوششي هست يا خير. بدين معنا كه هر نقطه از محيط هدف بوسيله حداقل k حسگر تحت پوشش قرار مي گيرد يا خير؟ به طوري كه K يك پارامتر داده شده است. بدين منظور هر حسگر محيط حسگري اش را بررسي مي كند تا مشخص كند كه آيا تمام ناحيه اش –kپوششي است؟ با جمع آوري اطلاعات تمام حسگرها يك جواب درست بدست مي آيد.

    نگارنده

    محمد احمدي نيا

    استاد راهنما

    دكتر محمد رضا ميبدي
    [1]
    S. Slijepcevic and M. Potkonjak, “Power Efficient Organization of Wireless Sensor Networks,” Proc. of IEEE International Conference on Communications, Vol 2, pp 472-476,Helsinki, Finland, June 2001.

    [2]
    M. Cardei, D. MacCallum, X. Cheng, M. Min, X. Jia, D. Li, and D.-Z. Du, “Wireless Sensor Networks with Energy Efficient Organization”, Journal of Interconnection Networks, Vol 3, No 3-4, pp 213-229, Dec 2002.

    [3]
    D. Tian and N. D. Georganas, “A Coverage-Preserving Node Scheduling Scheme for Large Wireless Sensor Networks,” Proc. of the 1st ACM Workshop on Wireless Sensor Networks and Applications, 2002.

    [4]
    W. R. Heinzelman, A. Chandrakasan, and H. Balakrishnan, “Energy-Efficient Communication Protocols for Wireless Microsensor Networks,” Proc. of HICSS, Jan 2000.

    [5]
    F. Ye, G. Zhong, S. Lu, and L. Zhang, “Energy Efficient Robust Sensing Coverage in Large Sensor Networks,” Technical Report UCLA, 2002.

    [6]
    C.-F. Huang and Y.-C. Tseng. The coverage problem in a wireless sensor network. In ACMInternational Workshop on Wireless Sensor Networks and Applications (WSNA), 2003, pp. 115–121.
     
وضعیت موضوع:
You must be a logged-in, registered member of this site to view further posts in this thread.

این صفحه را به اشتراک بگذارید