Summary
מחקר זה מספק שיטה לשימוש ביחידת מעבד קוונטי כדי לחשב את המסלולים עבור דינמיקות תעבורה שונות הפועלות כדי להשיג ביצועים טובים יותר משיטות קלאסיות בספרות כדי למקסם את חיי הרשת.
Abstract
שיטת שימור האנרגיה של רשת החיישנים, שהיא הכלאה של מחשב קלאסי ומעבד קוונטי, הוכיחה ביצועים טובים יותר מאלגוריתם היוריסטי המשתמש במחשב קלאסי. בכתב יד זה מוצג ומוצדק ההקשר הטכני למשמעות השיטה. לאחר מכן שלבי הניסוי מודגמים ברצף מבצעי עם איורים במידת הצורך. השיטה אומתה על ידי תוצאות חיוביות על פני קבוצת מדגם שנוצר באופן אקראי של טופולוגיות רשת. תוצאות הניסוי המוצלחות של שיטה זו סיפקו גישה טובה יותר לבעיות מקסום חיי רשת חיישנים והראו כי המעבד הקוונטי החדיש הנוכחי הצליח לפתור בעיות הנדסיות מעשיות גדולות עם יתרונות העוקפים את השיטות הנוכחיות בספרות. במילים אחרות, ניתן לנצל את היתרון הקוונטי למאמצים הטובים ביותר. זה עבר משלב הוכחת ההיתכנות לשלב הוכחת היתכנות.
Introduction
שימור אנרגיה ברשתות חיישנים היה נושא קריטי מאוד בתכנון1. שיטות קלאסיות בדרך כלל להתמודד עם הבעיה באמצעות גישה אד הוק 2,3,4,5,6. עם זאת, שיטות אלה מחקות את צמתי החיישנים כנכסים חכמים המנוהלים בנפרד שיכולים גם לשתף פעולה כדי לשרת הן את האינטרסים של הפרט והן של הקהילה. בשל הסביבה התנודתית שבה חיישנים עובדים, בחלק מהעבודות, אלגוריתמים אקראיים מוצגים על מנת ללכוד את אי הוודאות הסביבתית, בעוד שבאחרים, אינטליגנציה ביולוגית מושאלת כדי לפתח אלגוריתמים היוריסטיים שיכולים להשיג תוצאות מקובלות השכל הישר7. כדי להמחיש עוד, עבור אותם אלגוריתמים אקראיים, מצד אחד, אי ודאויות סביבתיות עשויות שלא להיות אקראיות כמו הרצף האקראי שנוצר על ידי מעבד קלאסי, מצד שני, גם אם אי הוודאות הסביבתית היא אקראית לחלוטין, הם לא יכולים להילכד על ידי סימולטור התהליך האקראי שנוצר על ידי המעבד הקלאסי; עבור אותם אלגוריתמים של אינטליגנציה ביולוגית, ראשית, לא נגזר ניתוח מתמטי קפדני כדי לגרום להוכחה מושגית לעבוד, שנית, ההתכנסות לאמת או גבול סובלנות השגיאה יכולים להיות מוגדרים רק בהינתן אמת קרקעית מושכלת - אם כי כמות משמעותית של עבודות בספרות הוכיחו במידה מסוימת כי אלגוריתמים היוריסטיים אלה עובדים, ראשית, אלגוריתמים אלה מנותחים (לא מדומים) מול תרחישי מקרה שימוש מוגדרים היטב, הם נעצרים בקריטריונים מסוימים שעדיין שווה להרהר בהם במחקר נוסף, עבור דבר אחר, כאמור, רוב האלגוריתמים לא אומתו מול סימולציית תוכנה שניתן לפרוס בקלות רבה יותר במיקרו-מעבדים שהופכים חיישן להיות8 שלו.
אנחנו לא מתייחסים כאן ללמידת מכונה (ML) כי היא צריכה להשתמש בניתוח נתונים שדורש נפח גדול יחסית של כוח חישובי שאינו נייד במכשירי חיישנים9.
כדי לענות על החששות שהוזכרו לעיל, אנו מספקים אלגוריתם קוונטי היברידי. האלגוריתם הוא היברידי בכך שמנגנון בחירת ראש האשכול מיושם באמצעות אלגוריתם אקראי קלאסי במהלך חישובי הניתוב המבוצעים באמצעות מעבד קוונטי לאחר הגדרת טופולוגיית הרשת. השיטה מוצדקת באופן הבא: (1) כפי שנדון בפסקה הראשונה בנוגע לאי-הוודאות הסביבתית, איננו רוצים להמשיך וליישם מחולל רצפים קוונטיים כדי ללכוד את הדינמיקה הסביבתית מכיוון שניתן לעקוב אחריה מבחינה היסטורית. הדינמיקה הסביבתית שניתן לעקוב אחריה היסטורית מוצדקת על ידי עבודות מחקר שונות של למידת מכונה במדעי הרשתות. בשלב הנוכחי אנחנו נשארים עם הגישה הקלאסית. (2) השיטה המדויקת המסתמכת על ניתוח מתמטי מופשט מבטיחה להגיע לאמת בסיסית. פיזיקה ניסויית קוונטית נתמכה עד כה בצורה מתוחכמת על ידי מתמטיקה פיזיקלית. יתר על כן, יישומי אלגוריתמים כמו אלגוריתם שור10 קיימים כדי להוכיח את התיאוריה המעוגלת הזו.
כמות מספקת של סקר ספרות מובאת להלן לשם השוואה. לפרוטוקול HEESR המוצע11 יש יתרונות מוכחים בתוצאות, אך המחברים ציינו היטב את פרמטרי תצורת הסימולציה, לדוגמה, פונקציית ההתפלגות האקראית המדויקת של מיקום הצומת, ההצדקה הנכונה של אחוז ראש האשכול p (0.2%), ופרמטר קנה המידה להתפלגות רמת האנרגיה (1-2 ג'אול) בין צמתים a_i. היא אסרה על המחבר להמשיך הלאה כדי לשכפל את הניסויים ולערוך את ההשוואה. מנגנון ניתוב הספק12 משתמש בשיטת התאמת העקומה כדי להעריך בקירוב פונקציות רציפות אחודות מערכות נתונים נפרדות המתקבלות ממרחב מדגם לא מוגדר עבור דטרמיננטים המשפיעים על תהליך ההחלטה של ניתוב הרשת האופטימלי. שיטת התאמת העקומה13 דורשת מידע מוקדם על טופולוגיית הרשת. בנסיבות אמיתיות ייתכן שלא יהיה מידע מוקדם זמין. גם כאשר קיים מידע מוקדם, טופולוגיית הרשת עשויה שלא להיות סדירה מספיק כדי שניתן יהיה למפות אותה לעקומות מתאימות המסוגלות להקל על חישוב נגזר. בהתאם לאותו היגיון, פרוטוקול DORAF14 לא הצדיק כיצד ומדוע לשאול את פונקציית בולצמן ואת הפונקציה הלוגיסטית כדי לקרב את קובעי הרשת. איסמעיל ואחרים 15 סיפקו התייחסות טובה למאמצי מחקר עתידיים לתכנון פרוטוקולי ניתוב חסכוניים באנרגיה ברשת התת-ימית.
Subscription Required. Please recommend JoVE to your librarian.
Protocol
1. הגדרת סביבת האוקיינוס של Dwave
- הורד והתקן את כלי האוקיינוס מהקישור: https://docs.ocean.dwavesys.com/en/stable/overview/install.html
- בטרמינל, סוג פיתון -m venv האוקיינוס.
- בטרמינל, הקלד . ים/פח/הפעל, כפי שמוצג באיור 1.
- בטרמינל, הקלד git clone https://github.com/dwavesystems/dwave-ocean-sdk.git
לאחר מכן, הקלד cd dwave-ocean-sdk, כפי שמוצג באיור 2.
לאחר מכן, הקלד python setup.py להתקין
איור 1: הפעלת סביבה וירטואלית באוקיינוס. חבילת Ocean, כפי שמשולבת D-wave API, מספקת חוויית משתמש מעוננת במחשב המשתמש עצמו להנחת המחשב של D-wave. אנא לחץ כאן כדי להציג גרסה גדולה יותר של איור זה.
איור 2: התקנת Ocean SDK. חבילת Ocean מספקת ערכות כלים נחוצות למפתחים, כולל התקנת Cplex שימושית. אנא לחץ כאן כדי להציג גרסה גדולה יותר של איור זה.
2. התקנת ממשק Cplex Python API
- הורדה והתקנה של Cplex: https://pypi.org/project/cplex/
- במסוף, הקלד pip להתקין cplex.
3. פרמטרי תצורת ניסוי
- הגדר את פרמטרי תצורת הניסוי המוזכרים בטבלה 1 באמצעות סימון תכנות Python בסקריפט, כפי שמוצג באיור משלים 1. לאחר הפעלת הסקריפט והפעלתו, השפה הבסיסית תעבד לאחסון המשתנים בזיכרון RAM. מצורף צילום מסך של קודי Python שבהם מוקצים לפרמטרים ערכים בהתאמה (איור משלים 1).
| D0 | 87.7085 מ' |
| E | 50 * 1 x 10-09 ג'אול |
| epson_fs | 1 * 10-12* 10 ג'אול |
| epson_mp | 0.0013 * 1 * 10-12 ג'אול |
| גודל מנה | 4000 סיביות |
טבלה 1: פרמטר מודל אנרגיה והגדרות גודל מנה.
תרשים משלים 1: סקריפט1. סקריפט להגדרת פרמטרי הניסוי. אנא לחץ כאן כדי להוריד קובץ זה.
4. סקריפטים של Python
- הכינו את סקריפטי Python ליצירת 198 מיקומי צומת חיישן דו-ממדיים המפוזרים באופן שווה לשישה סקטורים המחלקים את השטח המעגלי ברדיוס של 50 מ'.
הערה: הגרף המעגלי מחולק ל-6 סקטורים. בכל מגזר, המיקום של כל צומת מטופל בשני משתנים מתאימים. האחד הוא הזווית, והשני הוא הרדיוס. הקצה ערכים הן לזווית והן לרדיוס באמצעות מחולל התפלגות אקראית אחיד. ההליך המפורט מוצג באיור משלים 2 ובאיור משלים 3. - בתוך כל סקטור, ודא ש-33 צמתי החיישנים מפוזרים באופן אקראי על ידי התפלגות נורמלית. שמור את המיקומים הדו-ממדיים בקובצי טקסט לפי כל סקטור תחת כלל איות השם כ- 'posdata'+sector_no+'.txt' (איור 3 ואיור 4).
- פלחו את השטח המעגלי ברדיוס של 50 מ' לשישה סקטורים. הערכים הזוויתיים ההתחלתיים עבור ששת המגזרים הללו יוצרים את הווקטור A= [60,120,180,240,300,360].
- נניח שאינדקס המגזר הוא i, הגדר את אורך הקוטב עבור צומת חיישןj th כ - l_{i,j}=50*random.random()
- נניח שאינדקס המגזר הוא i, הגדר את הערך הזוויתי עבור צומת חיישןj th כ - ang_{i,j}=(60*random.random() + A_i - 60) * 2 * pi / 360
- הגדר את הקואורדינטות הקרטזיות של צומת חיישן jth בסקטורi כ -
x_{i,j}=l_{i,j}*cos(ang_{i,j})
y_{i,j}=l_{i,j}*sin(ang_{i,j})
- פלחו את השטח המעגלי ברדיוס של 50 מ' לשישה סקטורים. הערכים הזוויתיים ההתחלתיים עבור ששת המגזרים הללו יוצרים את הווקטור A= [60,120,180,240,300,360].
איור משלים 2: סקריפט2. סקריפט כדי להגדיר את מיקומי המיקום הדו-ממדיים עבור כל צומת לפי מגזר. אנא לחץ כאן כדי להוריד קובץ זה.
איור משלים 3: סקריפט3. קובץ Script לקביעת התצורה של כל ערכי מיקום צומת בתוך סקטור 1. אנא לחץ כאן כדי להוריד קובץ זה.
איור 3: מיקומי צמתים שנוצרו ואוחסנו מופרדים ל-6 קבצים שכל אחד מהם מתאים לסקטור אחד. מיקומי מיקום דו-ממדיים נשמרים בקובצי 6 posdata+'idx'. כל אחד מהם מציג מגזר. אנא לחץ כאן כדי להציג גרסה גדולה יותר של איור זה.
איור 4: מיקומי צמתים המאוחסנים בסקטור 0. המיקומים הם בשני ממדים ונוצרים באמצעות מחולל אקראי אחיד. העמודה הראשונה היא המיקומים האופקיים, והעמודה השנייה היא המיקומים האנכיים. אנא לחץ כאן כדי להציג גרסה גדולה יותר של איור זה.
5. הכנת רמות האנרגיה הראשוניות
- הכן את רמות האנרגיה הראשוניות עבור כל 198 צמתי החיישן. הקצה מחצית מהם עם אנרגיה התחלתית ב- 0.5 J והחצי השני עם אנרגיה התחלתית ב- 1 J. צור מערך לאחסון רמת האנרגיה של כל צומת, והשתמש בלולאה כדי להקצות לתאים המרוצפים במספרים זוגיים את הערך 1 ואת אלה המסודרים במספרים אי-זוגיים את הערך של 0.5. איור משלים 4 מציג את קודי Python, והתוצאה מוצגת באיור 5.
תרשים משלים 4: סקריפט4. סקריפט להקצאת מחצית האנרגיה של הצומת של 1 ג'אול ושאר 0.5 ג'אול. אנא לחץ כאן כדי להוריד קובץ זה.
איור 5: Energy_buffer המשימה הראשונית. מחצית מהצמתים מוקצים עם אנרגיה 1 ג'אול, בעוד החצאים האחרים מוקצים עם 0.5 ג'אול. אנא לחץ כאן כדי להציג גרסה גדולה יותר של איור זה.
6. הכנת סקריפט אלגוריתם Advanced_Leach (איור 6 ואיור 7)
- הכן סקריפט פונקציונלי שבו ראש האשכול נבחר ונוצר האשכול.
הערה: האשכול נבחר באמצעות לולאה בתנאי שמספר ראשי האשכולות שנבחר קטן מהמספר הכולל של צמתים חלקי 6. התנאי הוא להבטיח שבתוך כל אשכול, כמות צומת המקור שווה או קטנה מ- 6. בתוך הלולאה, לכל צומת מוקצה מספר אקראי בין [0,1]. אלה הקטנים ממספר קריטריונים נתון הופכים לראש האשכול, בעוד שאחרים הופכים לצמתי המקור. ההליך המפורט מוצג בתרשים משלים 5. לאחר מכן, בהינתן מאגר קבוע של ראשי אשכולות, שאר צמתי המקור בוחרים את ראשי האשכולות שלהם במרחק הקצר ביותר, בהתחשב בכך שראש האשכול עדיין לא אירח יותר מ-6 צמתי מקור. הנוהל המפורט מוצג בתרשים משלים 6.- הגדר T_n=P/(1-P*(count%(1/P)))), כאשר P = 0.2 (היחס היחסי בין מספר ראשי האשכולות לגודל הרשת הכולל) והספירה היא כמות השידור המעוגלת עד כה.
- עבור כל צומת חיישן, השג מספר אקראי בין[0,1] threshold_rm = אקראי.אקראי()
- אם threshold_rm קטן מ-T_n, בחר צומת חיישן זה כראש האשכול.
- עבור כל אחד מהצמתים שאינם cluster_head, בחר את צומת חיישן ראש האשכול הקרוב ביותר אליו כראש האשכול שלו. בהינתן מאגר קבוע של ראשי אשכולות, שאר צמתי המקור בוחרים את ראשי האשכולות שלהם במרחק הקצר ביותר, בהתחשב בכך שראש האשכול עדיין לא אירח יותר מ-6 צמתי מקור. הנוהל המפורט מוצג בתרשים משלים 6.
- הכן את שורות הפקודה כדי לחשב את תהליך דלדול האנרגיה ברחבי הרשת כולה עבור סבב זה. עבור כל הפעלה של האלגוריתם שמשלים אצווה אחת של משלוחים של המנות מצמתי המקור לכיור, מערך אגירת האנרגיה כפי שהוכן יעודכן כך שיהיה מופחת תא אחר תא בערכים. צריכת האנרגיה לאורך הנתיב תהיה סיכום צריכת האנרגיה לכל מסלול צומת לצומת, המחושב על פי מודל אנרגיה1. הנוהל המפורט מוצג בתרשים משלים 7.
- חשב את מדדי השידור העגולים הנדרשים.
הערה: לכל ריצה של האלגוריתם כדי להשלים אצווה אחת של מסירת מנות, מערך האנרגיה מתעדכן, כמות הריצה ומספר הצמתים המרוקנים נספרים. אם הערך גדול יותר או שווה ל- 1, אז FND (מת הצומת הראשון) שווה לסכום ההפעלה הנוכחי. אם הערך גדול יותר או שווה למחצית מסכום הצומת, אז HND(half node die) שווה לסכום ההפעלה הנוכחי. אם הערך שווה לסכום הצומת הכולל, אז AND (כל הצומת מת) שווה לסכום ההפעלה הנוכחי. הנוהל המפורט מוצג בתרשים משלים 8.
איור 6: מערך ראשי אשכולות. מספרי הרצף של הצמתים שנבחרו להיות ראשי האשכולות. אנא לחץ כאן כדי להציג גרסה גדולה יותר של איור זה.
איור 7: מערך אינדקס ראשי אשכולות. מכיוון שישנם שישה סקטורים, שלכל אחד מהם 33 צמתי חיישן, במערך אינדקס ראש האשכול, המספר מציין את מספר הרצף של ראש האשכול שאליו שייך צומת החיישן המתאים. מדד המיקום של המערך מתאים למספר הרצף של כל צומת חיישן. עבור צומת החיישן שנבחר כראש האשכול, המספר המוקצה לחריץ שלו במערך הוא מספר הרצף של עצמו. אנא לחץ כאן כדי להציג גרסה גדולה יותר של איור זה.
תרשים משלים 5: סקריפט5. סקריפט לבחירת ראש האשכול. אנא לחץ כאן כדי להוריד קובץ זה.
תרשים משלים 6: סקריפט6. קובץ Script להקצאת צמתי מקור לאשכולות. אנא לחץ כאן כדי להוריד קובץ זה.
תרשים משלים 7: סקריפט7. סקריפט לעדכון מאגר האנרגיה עבור כל צמתי המקור באמצעות הפחתת כמות האנרגיה הנצרכת באמצעות שידור. אנא לחץ כאן כדי להוריד קובץ זה.
תרשים משלים 8: סקריפט8. סקריפט לחישוב כמות העגלות כלפי מעלה שאליהן מת הצומת הראשון, וחצי מהצמתים מתים. אנא לחץ כאן כדי להוריד קובץ זה.
7. הכנת סקריפט אלגוריתם קוונטי היברידי
- הכן סקריפט מתפקד שבו ראש האשכול נבחר וראש האשכול נוצר.
- מכיוון שגודל הצביר המרבי הוא 6 בניסוי זה1, יש לוודא שכמות ראשי האשכולות אינה פחותה מ-current_valid_node_amount/6, הליך הבחירה יופעל בלולאה עד לעמידה בקריטריון זה.
הערה: אם current_valid_node_amount אינו גדול מ- 6, אז צמתים חוקיים אלה יוצרים אשכול אחד ורק אשכול עצמם. - עבור כל אחד מהצמתים שאינם cluster_head_valid, חשב את המרחק שלו לכל אחד מראשי האשכולות שנבחרו, והקצה לו את ראש האשכול שגודל האשכול שלו לא עלה על 6 כאשר ערך המרחק הוא הקטן ביותר.
הערה: באיור 8 מחושבים כל המרחקים של הצמתים שאינם cluster_head_valid לראש האשכול שנבחר 24, וכל ראש האשכול שנבחר מוצג באיור 9. איור 10 מציג את כל הצמתים מוקצים לראש האשכול המתאים להם, ואיור 11 מראה קיבוץ הצמתים החברים בכל אשכול במערך וקטורי.
- מכיוון שגודל הצביר המרבי הוא 6 בניסוי זה1, יש לוודא שכמות ראשי האשכולות אינה פחותה מ-current_valid_node_amount/6, הליך הבחירה יופעל בלולאה עד לעמידה בקריטריון זה.
- הכן את סקריפט תת-הפונקציה, שבו נוצרת בעיית מיטוב הניתוב לכל אשכול ונשלחת ל-API של גל D (איור 12). נתיבי הניתוב מחושבים אשכול אחר אשכול.
- באמצעות סקריפט Python, חשב את תהליך דלדול האנרגיה ברחבי הרשת כולה כדי להעריך כמותית את האלגוריתם לפי אורך חיי הרשת במונחים של מספר סבבי השידור.
הערה: עבור כל הפעלה של האלגוריתם שמשלים אצווה אחת של משלוחים של המנות מצמתי המקור לכיור, מערך אחסון האנרגיה כפי שהוכן יעודכן כך שהערכים יצטמצמו תא אחר תא. צריכת האנרגיה לאורך הנתיב תהיה סיכום צריכת האנרגיה למסלול מצומת לצומת, המחושב על פי מודל אנרגיה1. הנוהל המפורט מוצג בתרשים משלים 7. - באמצעות סקריפט Python, רשום את הרגע שבו הצומת הראשון מנוקז החוצה וכאשר מחצית הצמתים מרוקנים החוצה. הנוהל המפורט מוצג בתרשים משלים 8.
איור 8: toClusterHeadDistance Array עבור צומת שאינו cluster_head עם אינדקס 24. העמודה הראשונה היא המרחק והעמודה השנייה היא מספר אינדקס ראש האשכול לחץ כאן כדי להציג גרסה גדולה יותר של איור זה.
איור 9: מערך CHID_buff. מספרי רצף של צמתי החיישן שנבחרו כראשי האשכול. אנא לחץ כאן כדי להציג גרסה גדולה יותר של איור זה.
איור 10 מערך CHIdx_buff. מספר הרצף של צמתי חיישן ראש אשכול מוקצה לכל צומת חיישן מתאים. אנא לחץ כאן כדי להציג גרסה גדולה יותר של איור זה.
איור 11: מערך CH_BUFF. קבוצת אשכולות לכל צמתי חיישן ראש אשכול המתאימים למערך CHID_buff. כל קבוצת אשכולות מורכבת מ-0 או יותר מ-0 צמתי חיישן. כל מערך קבוצת אשכולות מציג את מספרי הרצף של צמתי החיישנים הנמצאים בו. אנא לחץ כאן כדי להציג גרסה גדולה יותר של איור זה.
תרשים 12: חישוב נתיבי ניתוב לכל מגזר. עבור כל מגזר, נתיבי הניתוב עבור כל צמתי המקור מחושבים. אנא לחץ כאן כדי להציג גרסה גדולה יותר של איור זה.
Subscription Required. Please recommend JoVE to your librarian.
Representative Results
תוצאות ממדגם ריצה אחד מוצגות בטבלה 2, טבלה 3 וטבלה 4. ערכות הנתונים המפורטות עבור שלוש אצוות הנתונים זמינות בתיקייה Supplementary Data 1 .
| ערכת נתונים 1 | ||
| 198 צמתים באזור מעגלי ברדיוס של 50 מ ' | אלגוריתם קוונטי היברידי | Advanced_Leach אלגוריתם |
| FND | 1442 | 727 |
| HND | 2499 | 1921 |
טבלה 2: אצווה 1 של תוצאות הניסוי.
| ערכת נתונים 2 | ||
| 198 צמתים באזור מעגלי ברדיוס של 50 מ ' | אלגוריתם קוונטי היברידי | Advanced_Leach אלגוריתם |
| FND | 757 | 1463 |
| HND | 1925 | 2500 |
טבלה 3: אצווה 2 של תוצאות הניסוי.
| ערכת נתונים 3 | ||
| 198 צמתים באזור מעגלי ברדיוס של 50 מ ' | אלגוריתם קוונטי היברידי | Advanced_Leach אלגוריתם |
| FND | 790 | 1461 |
| HND | 1888 | 2500 |
טבלה 4: אצווה 3 של תוצאות הניסוי.
שלושה מדדים נבחרים עם הגדרות4 כמפורט להלן:
FND - הצומת הראשון למות. מספר השידורים המעוגלים כלפי מעלה שאליהם מנוקזת אנרגיית צומת החיישן הראשונה;
HND - חצי צומת למות. מספר השידורים מתעגל כלפי מעלה שאליו מתרוקנת מחצית מהאנרגיה של צמתי החיישן;
LND - הצומת האחרון למות. מספר השידורים מתעגל כלפי מעלה שאליו כל רשת החיישנים מתה.
מהתוצאות ניתן לראות שלאלגוריתם הקוונטי ההיברידי יש יעילות רבה יותר מאשר לאלגוריתם advanced_leach.
תוצאות נוספות של מורכבות הזמן של השיטה המוצעת ושל תרשים הציות מוצגות באיור 13 ובאיור 14, בהתאמה.
איור 13: סיבוכיות הזמן של האלגוריתם הקוונטי ההיברידי. הזמן ביחידת השנייה שהוקדש להפעלת מחזור אחד של HQA על פני גדלי רשת שונים. אנא לחץ כאן כדי להציג גרסה גדולה יותר של איור זה.
איור 14: תוצאות האלגוריתם הקוונטי ההיברידי התואם לאלגוריתם Advanced Lach. FND ו- HND או HQA ו- ALA חולקים תבנית צורת עלילה דומה. אנא לחץ כאן כדי להציג גרסה גדולה יותר של איור זה.
נתונים משלימים 1: מערך הנתונים של שלוש קבוצות הניסויים שבוצעו במחקר זה. אנא לחץ כאן כדי להוריד קובץ זה.
Subscription Required. Please recommend JoVE to your librarian.
Discussion
המעבד הקוונטי המסחרי החדיש הנוכחי יכול לשמש בבעיות חישוביות של כל טופולוגיית רשת1. יישום מעבד קוונטי אינו מוגבל על ידי מספר ה-qbits הפיזיים שאף אחד מהמעבדים הקוונטיים הצליח ליישם.
בתכנון הארכת חיי רשת חיישנים, התוצאות מראות התקדמות בשיטה להשגת חיי רשת ארוכים עוד יותר באמצעות מעבד קוונטי. התוצאות מרמזות כי היתרון הקוונטי מוכן לניצול מסחרי הן במגזר הציבורי והן במגזר הפרטי.
מבחינת השלכות ניהוליות, Quantum Advantage יכולה להיות אבן הדרך הבאה שתסלול דרך מבטיחה לשגשוג בר-קיימא של היי-טק בעתיד הקרוב. ההיי-טק הנוכחי, במונחים של אסטרטגיית למידה ו/או בינה מלאכותית (AI), דורש בכל שיטה את כונן הכוח כדי לעבד/להחזיק את הנתונים. מנקודת מבט ברמה גבוהה של הגלובוס הירוק, הוא אינו בולט כמועמדת טובה16. ML/AI למרות שהוא הופך את החישוב ליעיל יותר מבחינה כלכלית, אינו מספק פתרון אנליטי לשורש הסיבה מכיוון שמחשוב יעיל נסחר על ידי מתקני חישוב בעלי הספק גבוה. לכן, הם מוגבלים ביסודם על ידי המחשב בעל הביצועים הגבוהים (HPC). מחשוב קוונטי, אשר מחולל מהפכה בפרדיגמת המחשוב, הוכח כיעיל במחשוב מהיר יותר ממחשבים מדור קודם ביישומי ניסוי מעשיים מרובים 17,18. ML בסיוע קוונטי, מבחינת המחבר, הוא PML (למידת מכונה הסתברותית). אלגוריתם ML (סקריפט/שפת תכנות ברמה גבוהה-נמוכה) פועל על התקן מחשוב שיכול להיות מחשב קלאסי או מחשוב קוונטי. בהינתן אותו אלגוריתם ML של שורות פקודה ניתנות להפעלה n, תן ל-f_cc(n) לציין את הצריכה בחישוב עבור מחשבים קלאסיים ו-f_qc(n) לציין את הצריכה בחישוב עבור מחשבים קוונטיים. f_cc(n) הוא סיכום משוקלל של צריכה חישובית של alpha_i הפעלה קלאסיות של המחשב עבור n שורות הפקודה. f_qc(n) הוא סיכום משוקלל שווה של צריכה חישובית של alpha_j הפעלה של מחשב קוונטי עבור אותן n שורות פקודה. המשקולות נשארות ללא שינוי מכיוון ששורות הפקודה של ML ברמה העליונה זהות באותה מידה. במילים פשוטות, עבודה זו ועבודה קודמת1 הראו כי alpha_j הוא תמיד פחות מ alpha_i ולכן f_qc(n) הוא תמיד פחות מ f_cc(n).
באשר להשלכות אקדמיות, מעבדים / מתקני מחשוב שהוקמו בעבר משמשים באופן מסורתי כדי לסייע לחוקרים לחשוב/ליצור/לפתח את רעיונותיהם ותוכניותיהם. המחשוב הקוונטי מצביע על כך שהגישה המתודולוגית של החוקרים ממתינה להתפתחות אפית. זה יכול להיות משבש אבל אופטימי. מעתה, חוקרים שאינם רגילים לתכנון/ניתוח אלגוריתמים תיאורטיים צריכים לעבוד יד ביד כדי להמציא/ליצור אלגוריתמים קוונטיים כדי לפתור את נושא המחקר שלהם. רוב האלגוריתמים הקוונטיים למחקר מעשי אינם זמינים. במשפט אחד השתנו מכשירי המחשוב של החוקרים. הגדרת סביבה וירטואלית ו- QPU API מסתמכים לחלוטין על חיבור אינטרנט משביע רצון.
מגבלות המחקר כוללות: (i) קיבולת הקישור לא נחשבה1. המערכת מתעלמת משיעור אובדן המנות. עבודות עתידיות ישקלו את פרוטוקול רשת החיישנים הבסיסי כדי לנסח כראוי את הבעיה בהתחשב הן בצריכת האנרגיה והן בבקרת אובדן (עם סכימת שידור מחדש או לא). (ii) מניחים כי טופולוגיית הרשת ידועה מראש. מיקומי הצומת קבועים. (iii) הזמן הדרוש להפעלת האלגוריתם הקוונטי ההיברידי בכל סיבוב ארוך יותר מאלגוריתם Advanced Leach אך ברמת דיוק גבוהה יותר. (iv) האלגוריתם לא הצליח לעבוד במצב לא מקוון.
Subscription Required. Please recommend JoVE to your librarian.
Disclosures
ללא
Acknowledgments
העבודה נתמכת על ידי מועצת המחקר להנדסה ומדעי הפיזיקה של בריטניה (EPSRC) מענק מספר EP/W032643/1.
Materials
| Name | Company | Catalog Number | Comments |
| Dell Laptop | Dell | N/A | |
| Ubuntu 18.04.6 LTS | Canonical Ltd | 18.04.6 LTS | |
| Python3.8 | Python Software Foundation | 3.8.0 | |
| Dwave QPU | Dwave | https://docs.ocean.dwavesys.com/en/stable/overview/install.html |
References
- Chen, J., Date, P., Chancellor, N., Atiquazzaman, M., Cormac, S. Controller-based energy-aware wireless sensor network routing using quantum algorithms. IEEE Transactions on Quantum Engineering. 3, 1-12 (2022).
- Lin, H., Uster, H. Exact and heuristic algorithms for data-gathering cluster-based wireless sensor network design problem. IEEE/ACM Transactions on Networking. 22 (3), 903-916 (2014).
- Zhou, Y., Wang, N., Xiang, W. Clustering hierarchy protocol in wireless sensor networks using an improved PSO algorithm. IEEE Access. 5, 2241-2253 (2017).
- How long is the lifetime of a wireless sensor network. Seah, W. K. G., Mak, N. H. 2009 International Conference on Advanced Information Networking and Applications, Bradford, UK, , 763-770 (2009).
- Salahud din, M., Rehman, M. A. U., Ullah, R., Park, C., Kim, B. S. Towards network lifetime enhancement of resource constrained IoT devices in heterogeneous wireless sensor networks Sensors. 20, 4156 (2020).
- Wu, W., Xiong, N., Wu, C. Improved clustering algorithm based on energy consumption in wireless sensor networks. IET Network. 6 (3), 7-53 (2017).
- Kumar, N., Kumar, V., Ali, T., Ayaz, M. Prolong network lifetime in the wireless sensor networks: An improved approach. Arabian Journal for Science and Engineering. 46, 3631-3651 (2021).
- Faris, H., Aljarah, I., Al-Betar, M. A., Mirjalili, S. Grey wolf optimizer: A review of recent variants and applications. Neural Computing and Applications. 30, 413-435 (2018).
- Kaur, J., Arifkhan, M., Iftikhar, M., Imran, M., Haq, A. Machine learning techniques for 5G and beyond. IEEEAccess. 9, 23472-23488 (2021).
- Shor, P. Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAMJournalonComputing. 26 (5), 1484-1509 (1997).
- Qabouche, H., Sahel, A., Badri, A. Hybrid energy efficient static routing protocol for homogeneous and heterogeneous large scale WSN. Wireless Networks. 27, 575-587 (2021).
- Farooq, M., et al. POWER: probabilistic weight-based energy-efficient cluster routing for large-scale wireless sensor networks. The Journal of Supercomputing. 78, 12765-12791 (2022).
- Maddams, W. F. The scope and limitations of curve fitting. Applied Spectroscopy. 34 (3), 245-267 (1980).
- Wang, X., et al. A dynamic opportunistic routing protocol for asynchronous duty-cycled WSNs. IEEE Transactions on Sustainable Computing. , (2023).
- Ismail, A. S., Wang, X., Hawbani, A., Alsamhi, S., Aziz, S. Routing protocols classification for underwater wireless sensor networks based on localization and mobility. Wireless Networks. 28, 797-826 (2022).
- Garcia-Martin, E., Rodrigues, C. F., Riley, G., Grahn, H. Estimation of energy consumption in machine learning. Journal of Parallel Distributed Computing. 134, 75-88 (2019).
- Egger, D. J., et al. Quantum computing for finance: State-of-the-art and future prospects. IEEE Transactions on Quantum Engineering. 1, 1-24 (2020).
- Rasool, R. U., Ahmad, H. F., Rafique, W., Qayyum, A., Qadir, J. Quantum computing for healthcare : A review. TechRxiv. , (2021).
