כיסוי מחסום ע"י מישמרות של חיישנים נייחים

Barrier Coverage using Duty Cycles of Static Sensors

הפרוייקט יעסוק בבעיה של תזמון חיישנים שממוקמים לאורך מחסום קווי שמיוצג ע"י הקטע [0,N]. החיישנים נייחים, ולכל אחד יש מקור אנרגיה מוגבל. אם חיישן i, שממוקם בנקודה x_i, מקבל רדיוס כיסוי r_i, אז הוא מכסה את הקטע [x_i-r_i,x_i+r_i]. צריכת האנרגיה של החיישן במקרה זה היא r_i^a לכל יחידת זמן, כאשר a >= 1, ולכן הוא יכול לעבוד במשך b_i/r_i^a זמן, כאשר יש לו בטריה שקיבולה b_i. החיישנים אמורים לכסות את המחסום במשמרות בגודל מוגבל, כאשר המטרה היא לכסות את המחסום לכמה שיותר זמן.
במסגרת הפרוייקט הסטודנטים ילמדו על אלגוריתמי קירוב לפתרון הבעיה וגירסאות שלה, ויבחנו את ביצועיהם באמצעות סימולציות. בפרט, ביצועי האלגוריתמים יושוו לביצועים שמובטחים מהניתוח התיאורטי שלהם, לאלגורימים נאיביים, ולפתרונות סופר-אופטימליים שמחושבים ע"י תכנות לניארי. ניתן יהיה גם להשתמש במערכת הסימולציות על מנת לבחון אלגורתמים חדשים לבעיה.

דרישות:

יש לקחת את אחד הקורסים הבאים במהלך השנה:

(1) תכנון וניתוח אלגוריתמים (83456)

או

(2) גיאומטריה חישובית ויישומה ברובוטיקה (83655).

מקורות:

Amotz Bar-Noy, Ben Baumer, and Dror Rawitz. Changing of the guards: Strip cover with duty cycling. Theoretical Computer Science 610:135-148, 2016.
http://www.eng.biu.ac.il/~rawitzd/Papers/duty_cycle.pdf

Introduction to Algorithms. Cormen, Leiserson, Rivest, and Stein. MIT Press, 2009.