بخشی از مقاله
چکیده
خدمات مکانمبنا دستهای از خدمات آگاه به مکان هستند که در آنها با توجه به مکان کاربران به آنها خدماتی ارائه میشود. دستهای از این خدمات درخواستهای نزدیکترین همسایه به گروه - GNN - هستند. در این درخواستها گروهی از کاربران نقطهای با کمترینمجموع فاصله به همه اعضای گروه را تقاضا میکنند. در حین انجام درخواستهای مکانمبنا احتمال دارد که از اطلاعات مکانی کاربران سو استفاده شود. بنابراین لازم است حریم مکانی کاربران توسط روشی حفظ شود. در این مقاله، روشی برای انجام پرسوجوهای نزدیکترین همسایهی گروهی با حفظ حریم مکانی کاربران ارائه شده است. در روش ارائه شده هر یک از اعضای گروه ناحیهی بینشانی خود را به فراهمکنندهی خدمت اعلام میکند؛ فراهمکنندهی خدمت پس از دریافت تمام نواحی بینشانی، پرسوجو را پردازش کرده و مجموعهای از جوابهای کاندیدا را که شامل جواب حقیقی است به کاربران بازمیگرداند. درنهایت کاربران با استفاده از الگوریتمهای شایعهی مورد استفاده در تجمیع دادهها، جواب حقیقی را به دست میآورند، بهطوریکه نه خدمات دهنده و نه هیچیک از اعضای گروه نتوانند مکان حقیقی عضو دیگری را حدس بزنند. نتایج حاصل از ارزیابیهای انجامشده نشان میدهد که روش ارائهشده میزان حفاظت از حریم مکانی و زمان پاسخ به کاربران را نسبت به روشهای پیشین بهبود میبخشد.
کلمات کلیدی:خدمات مکانمبنا، نزدیکترین همسایهی گروهی، حریم مکانی، الگوریتم شایعه
-1 مقدمه
در حوزهی محاسبات فراگیر1 سیستمهای جدیدی به نام خدمات مکانمبنا2 - LBS - طراحی شدهاند که امکان پرسوجوهای مبتنی بر مکان را برای کاربران فراهم میکنند. این دسته از خدمات در صنایع نظامی و دولتی، خدمات اورژانس، خدمات تجاری و خدمات اطلاعاتی و برنامهریزی سفر و سرگرمی کاربرد دارند 3]،2،.[1 بهعنوانمثال، یک پرسوجو میتواند این باشد که »نزدیکترین عابر بانک به من کجا است؟.« ممکن است گروهی از کاربران مایل به یافتن نزدیکترین مکان مناسب برای ملاقات باشند، یعنی مکانی که مجموع فواصل پیموده شده توسط آنها را کمینه کند. به این مسئله یافتن نزدیک ترین همسایه گروهی3 یا GNN گفته می شود.
تاکنون الگوریتمهای مختلفی برای جستجوی نزدیکترین همسایه و نزدیکترین همسایه گروهی پیشنهاد شده است، حتی نسخههای فازی آنها نیز مطرحشدهاند 4]و[5، مسئله مورد بررسی در این پژوهش، انجام درخواست نزدیکترین همسایه گروهی در عین حفظ حریم مکانی اعضای گروه است زیرا این امکان وجود دارد که این خدمات حریم خصوصی4 افراد را به خطر بیاندازند؛ به این صورت که از مکان افراد در راستای اهدافی که مدنظر آنها نیست استفاده شود. پس لازم است توسط راهکاری در عین ارائه خدمات مورد نظر، حریم مکانی افراد نیز حفظ شود.تاکنون برای حفظ حریم مکانی اعضای گروه راهکارهای مختلفی ارائه شده[6] که هرکدام نقاط ضعف و قوت خود را دارند. در بعضی از آنها با استفاده از یک هماهنگکننده سعی در حفظ حریم مکانی اعضای گروه شده است که همین لزوم اعتماد به هماهنگکننده میتواند حریم مکانی اعضای گروه را به خطر بیاندازد. در بعضی روشهای دیگر اگر تبانی بین یکی از اعضای گروه و خدمات دهنده اتفاق بیافتد، حریم مکانی دیگر اعضای گروه به خطر می افتد.
در این پژوهش ایده جدیدی برای حفظ حریم مکانی کاربران در پرس و جو های نزدیک ترین همسایه گروهی مطرح شده است که در آن با استفاده از سازوکار شایعه در تجمیع دادهها5 پاسخ پرس و جوی GNN محاسبه می شود. در روش ارائه شده با استفاده از یک فیلتر خصوصی6 بر اساس شایعه اقدام به محاسبه و انتخاب گزینه مناسب از میان کاندیداهای ارسالی از سمت خدمات دهنده می شود که بدین ترتیب حریم مکانی افراد نه تنها در مقابل خدمات دهنده بلکه در مقابل سایر کاربران نیز حفظ میشود.ساختار مقاله در ادامه بهصورت زیر است: در بخش دوم برخی از کارهای انجامشده در زمینه حفظ حریم مکانی حین درخواستهای گروهی مطرح میشود. در بخش سوم مرور مختصری بر سازوکار تجمیع داده مبتنی بر شایعه که روش پیشنهادی از آن استفاده می کند کرده ایم. بعد از آن در بخش چهارم به معرفی روش پیشنهادی می پردازیم. در بخش پنجم نتایج حاصل از شبیه سازی و ارزیابی روش پیشنهادی ارائهشده است. نهایتاً بخش ششم مقاله به جمع بندی پژوهش و معرفی فعالیتهای آتی اختصاص پیدا کرده است.
-2 کارهای مرتبط
یکی از راهکارهای ارائه شده برای انجام درخواستهای مکانمبنا این است که پرسوجوها در دو مرحله انجام شود. در مرحله اول توسط معیار بینشانی محل اعضای گروه نادقیق شده و برای خدمات دهنده ارسال شود تا خدمات دهنده از محل دقیق کاربران اطلاع پیدا نکند و بدینصورت حریم مکانی اعضا در برابر خدمات دهنده حفظ شود. در مرحله دوم از آنجاییکه خدمات دهنده از محل دقیق کاربران اطلاع ندارد نمیتواند پاسخ دقیق را برای کاربران بازگرداند و بنابراین خود کاربران باید محل دقیق را با همکاری یکدیگر پیدا کنند بهنحویکه مکان هیچکدام برای دیگری فاش نشود. به این سازوکار، فیلتر خصوصی می گویند.
در مورد حفظ حریم مکانی با استفاده از معیار بینشانی، اولین بار در سال 2003، یک روش متمرکز به نام مخفی سازی مکانی-زمانی - مخفی سازی بازهای - [7] ارائه شد که در آن، بی نشانکننده، مکان کاربر را در یک ناحیهی مکانی شامل حداقل k-1 کاربر دیگر پنهان میکند. پسازآن در سال 2005، در روش مخفی سازی گروهی [8] تعیین مقدار k و بیشینهی مساحت ناحیهی بینشانی بر عهدهی کاربران گذاشته شد. این روش سربار محاسباتی بالایی دارد و تنها زمانی مناسب است که مقدار k دلخواه کاربر کوچک باشد.در سال 2006، یک روش متمرکز به نام [9] Casper ارائهشده است که در آن کاربران نیازمندیهای خود را برحسب مقدار k و کمینهی مساحت دلخواه بیان میکنند. بی نشانکننده، با کمک یک جدول درهمسازی7، اطلاعات
مکانی کاربران را در یک ساختمان دادهی هرمی ذخیره کرده و طی یک جستجوی پائین به بالا ناحیهی بینشانی دلخواه کاربر را ایجاد میکند.در سال 2010، هاشم و همکارانش، یک راهکار غیرمتمرکز ارائه کردهاند [10] که در آن کاربران میتوانند هویت، مکان و نوع خدمت درخواستی خود را از افراد دیگر مخفی کنند؛ برای این منظور، از قابلیت دستگاههای سیار در ایجاد شبکههای بیسیم شخصی استفاده میشود. در این مقاله، کاربران برای مخفی ساختن مکان دقیق خود از همسایگانشان از یک ناحیهی مخفی محلی و برای حفظ حریم مکانی در برابر فراهمکنندهی خدمت از یک ناحیهی مخفی عمومی استفاده میکنند.در کار انجام شده در [11] عاشوری و همکارانش از میانگین نقاط برای انجام پرسوجو استفاده میکنند. این روش برای مخفی نگهداشتن مکان پرسوجو کنندگان در فرآیند محاسبهی مرکز ثقل، از رمزنگاری همومورفیک8 کمک میگیرد که در آن ابتدا کاربران مرکز ثقل خودشان را محاسبه میکنند و سپس به خدمات دهنده میفرستند.
در مقالهی [12] پرسوجوهای GNN در خدمات مکانمبنا را پرسوجوهای GNN خصوصی نامیده است. در این روش که از معماری غیرمتمرکز استفاده میکند، اعضای گروه قبل از انجام پرسوجو، یک کاربر هماهنگکننده را بهطور تصادفی انتخاب میکنند تا به آنها در انجام پرسوجوی GNN کمک کند.در این مقاله، دو نوع فیلتر خصوصی ارائه شده است. در روش اول که فیلتر خصوصی با هرس نهایی - SUM_FPPF - 9 نامیده شده است اگر - , ℎ - ، تابعی باشد که حداکثر فاصلهی اقلیدسی بین یک ناحیهی Ri و یک نقطهی ph را محاسبه میکند، فراهمکننده برای هر نقطهی دادهای - ph - که در مجموعه جواب قرار میگیرد، مقدار زیر را با توجه به نواحی بینشانی کاربران Ri - ها - محاسبه میکند:
ایدهی کلی این است که مجموعه جواب کاندیدا، به همراه حداکثر فاصلهی تجمعی تا هر جواب، بین کاربران ردوبدل گردد و هر کاربری که مجموعه جواب را دریافت میکند، هریک از فاصلههای تجمعی را با استفاده از رابطهی زیر بهروز کند:
در این رابطه - , ℎ - ، بیانگر فاصلهی حقیقی کاربر ui تا نقطهی دادهی ph است. در این صورت، مقادیر نهایی برابر با فاصلهی تجمعی حقیقی کاربران است.یک فیلتر خصوصی با هرس افزایشی - SUM_IPPF - 10 نیز ارائه شده است که در آن، هر کاربر با توجه به حداقل فاصلههای تجمعی، جوابهایی که امکان ندارد جزء جوابهای حقیقی باشند را از مجموعه جواب حذف میکند.کاربران، حداکثر و حداقل فاصلههای تجمعی را مطابق رابطههای 2و 3 بهروز میکنند. - 3 - کاربر، پس از بهروز کردن این فاصلهها، از بین حداکثر فاصلههای تجمعیجوابها، kاُمین کوچکترین مقدار - MaxDistk - را پیدا کرده و جوابهایی که حداقل فاصلهی تجمعیشان از این مقدار بزرگتر است را حذف میکند؛زیرا در مجموعه جواب، k تا جواب وجود دارد که حداکثر فاصلهشان از حداقل فاصلهی این جوابها کمتر است.
در این روش، تحت برخی شرایط فراهمکننده خدمت از مکان اعضای گروه با خبر میشود؛ و این روش وابستگی زیادی به فراهمکنندهی خدمت دارد. همچنین نسبت به حملهی تبانی جزئی آسیبپذیر است،مثلاً اگر یکی از کاربران با خدمات دهنده تبانی کند مکان سایر اعضای گروه به خطر میافتد.راهکار ارئه شده در این پژوهش یعنی استفاده از الگوریتم شایعه برای یافتن گزینه مناسب در میان کاندیدهای ارسالی از طرف خدمات دهنده دو مزیت دارد. اولین مزیت آن این است که نیاز به هماهنگ کننده ندارد، که باعث افزایش امنیت حریم مکانی اعضای گروه میشود. دومین مزیت آن این است که در صورت وقوع تبانی بین اعضای گروه و یا بین عضوی از گروه و خدمات دهنده حریم مکانی سایر اعضای گروه به خطر نمیفتد.
-3 الگوریتمهای شایعه برای تجمیع داده
روشهای شایعه، برای انتشار دادهها11 در شبکه و یا تجمیع دادهها12 مورداستفاده قرار میگیرند.[13] تجمیع دادهی مبتنی بر شایعه در چند دور - تراکنش - انجام میشود. در هر تراکنش از الگوریتم، هرکدام از گرهها بهطور تصادفی با یک یا چند تا از گرههای مجاور خود ارتباط برقرار کرده و مقدار ذخیرهای خود را در اختیار آنها قرار میدهد. در طول این تعاملها، گرهها مقدار ذخیرهایشان را با توجه به مقدار قبلی خود و مقدار دریافت شده و تابع تجمعی دلخواه، بهروز میکنند. این بهروزرسانی، مقدار گرهها را بهطور مجانبی به مقدار تجمعی حقیقی نزدیک میکند. دقت مقدار محاسبهشده، بستگی به تعداد دورهای الگوریتم دارد. از این روش میتوان برای محاسبه مقادیر تجمعی بهره برد بهنحویکه با ضرب تعداد گرهها در مقدار میانگین محاسبهشده توسط گرهها مقدار تجمعی به دست میآید.جهت تضمین محرمانه ماندن مقادیر گرهها، روش مبتنی بر افزودن نویز در الگوریتم شایعه، توسط موسیزاده و همکارانش ارائه شده است .[14] بدین نحو که هر گره - هر عضو گروه - مقداری نویز به مقدار واقعی خود اضافه میکند و سپس در طی تکرارهای الگوریتم اثر آن نویز را از بین میبرد.
-4 روش پیشنهادی
در این مقاله، فرض بر این است که کاربران میتوانند با استفاده از دستگاههای بیسیم مجهز به GPS، از طریق یک شبکه - مانند شبکهی سلولی و یا اینترنت - باهم ارتباط برقرار کنند.فرض کنید گروهی متشکل از n کاربر 1, 2, ⋯ , ، که به ترتیب در مکانهای 1, 2, ⋯ , قرار دارند، قصد دارند نزدیکترین نقطهی موردعلاقه به گروهشان را پیدا کنند؛اگر مکان تمام اعضای گروه بهصورت مبهم در اختیار فراهمکننده قرار گیرد و یا یک شاخص مکانی از اعضای گروه - مانند مرکز ثقل در روش SPM - [15] به فراهمکننده اعلام شود، فراهمکننده، نمیتواند جوابهای دقیق را به کاربران بازگرداند و به همین دلیل مجموعهای از جوابهای کاندیدا را به آنها بازمیگرداند. بنابراین، اعضای گروه باید خودشان جواب صحیح را از آن مجموعه استخراج کنند، بهطوریکه مکان هیچ عضوی از گروه، برای هیچکسی فاش نشود. این کار با استفاده از فیلترهای خصوصی انجام میشود.روند انجام پرسوجوهای kGNN، شامل چهار مرحلهی کلی است:
- 1درخواست انجام پرسوجوی گروهی از فراهمکنندهی خدمت.
- 2ارسال نواحی بینشانی کاربران به فراهمکنندهی خدمت.
3 - پردازش پرسوجو توسط فراهمکنندهی خدمت و ارسال جوابهای کاندیدا به تمام کاربران.
- 4 استفاده از فیلتر خصوصی توسط اعضای گروه جهت یافتن k جواب حقیقی.
مسئله بعدی نحوهی یافتن k نزدیکترین همسایهی حقیقی از میان جوابهای کاندیدا است، در این مقاله از الگوریتم شایعه استفاده خواهد شد که در آن، گرهها طی چندین تراکنش متوالی، بهصورت دوبهدو و بهطور موازی مقادیر خود را بین هم ردوبدل کرده و با توجه به مقادیر دریافتی و نیز تابع تجمعی مربوطه، مقدار ذخیرهشدهی خود را بهروز میکنند. این روشها به سرعت به مقدار واقعی، همگرا میشوند.اگر فاصلهی حقیقی هر کاربر ui - که در مکان li حضور دارد - تا نقطهی داده ی ph بهصورت - , ℎ - نشان داده شود و تعداد کاربران n تا باشد، فاصلهی تجمعی حقیقی تا نقطهی ph از رابطهی - 3 - به دست میآید.
برای محاسبهی مجموع مقادیر اولیه، میتوان میانگین مقادیر را با استفاده از الگوریتم شایعه محاسبه کرده و با ضرب آن در تعداد کاربران، مجموع مقادیر را بهطور تقریبی به دست آورد که در این صورت روش نسبت به حملهی تقاطع فواصل آسیبپذیر میشود. حمله تقاطع فواصل به حملهای گفته میشود که مهاجم با داشتن فاصله فردی تا سه نقطه میتواند مکان دقیق فرد را محاسبه کند. میتوان با استفاده مناسب از حداکثر فواصل تجمعی که فراهمکنندهی خدمت ارائه میکند این ضعف را برطرف کرد. در ادامه به دو روش ارائه شده در این پژوهش خواهیم پرداخت. روش اول که پایه روش دوم است دارای یک نقطه ضعف امنیتی است که به آن اشاره خواهد شد. برای حل این نقطه ضعف روش دوم ارائه می شود.
-1-4 فیلتر خصوصی مجموع مبتنی بر شایعه
اگر - , ℎ - ، نشاندهندهی حداکثر فاصلهی اقلیدسی بین یک ناحیهی تا یک نقطهی ℎ باشد، رابطه - 5 - مقداری که توسط فراهمکنندهی خدمت برای هریک از جوابها بازگردانده را نشان میدهد.
تمام اعضای گروه میتوانند مقادیر - , ℎ - و - , ℎ - را نیز محاسبه کنند. بنابراین رابطه - 6 - حاصل میشود.در رابطهی - 6 - ، اگر تفاضل فاصلهی تجمعی حقیقی و حداکثر فاصلهی تجمعی تا نقطهی ph را با diff - ph - نشان دهیم، رابطه - 7 - حاصل میشود.بنابراین هر کاربر برای هر نقطهی داده، مقدار اولیهی زیر را در نظر میگیرد:
