آماگ
۲۸ بهمن ۱۴۰۴، ۱۰:۲۴

چه الگوریتمی باید برای مکان‌یابی وای‌فای استفاده کنم؟

مورد استفاده: تحویل گرفتن از مدرسه (به‌روزرسانی) به‌جای مثالِ حیاطِ خلوتِ اصلی در پایین، بهتر است به یک مورد استفاده‌ی ملموس‌تر برویم. پلیس محلی شروع به برخورد با استفاده از پیامک و تماس تلفن همراه در محدوده‌های مدارس کرده است. این مسئله برای والدینی که بعد از یک مراسم در مدرسه‌ی راهنمایی بچه‌هایشان را تحویل می‌گیرند، دردسر ایجاد می‌کند. حتی برای آن‌هایی که قانون را نادیده می‌گیرند، وقتی صدها بچه هم‌زمان با والدینشان تماس می‌گیرند، دکل تلفن همراه به‌سرعت بیش از حد اشباع می‌شود. محوطه‌ی دانشگاه بزرگ است و پوشش وای‌فای دارد. به نظر می‌رسد باید بتوان اپلیکیشن موبایلی نوشت که به کاربر تلفن همراه اجازه دهد پیامکی حاوی فهرستِ قدرت سیگنال‌های وای‌فای به یک سرویس وب ارسال کند. سپس آن سرویس وب یک موقعیت‌یابی ایجاد کرده و پیام را به دستگاه ناوبریِ داخل ماشینِ والد بفرستد. سپس والد به محل صحیحِ داخل محوطه می‌رود. مثال حیاطِ خلوت (اصلی) وقتی لپ‌تاپم را به حیاطِ خلوت می‌برم و گزینه‌ی «مشاهده‌ی شبکه‌های موجود» را انتخاب می‌کنم، فهرستی از ۴ شبکه‌ی همسایه‌هایم را می‌بینم. هنگام راه رفتن، قدرت سیگنالِ نسبی از همسایه‌ها تغییر می‌کند. می‌خواهم با لپ‌تاپ در مکان‌های مشخصِ حیاطِ خلوت بایستم، روی نقشه کلیک کنم و نقاطی با ۴ قدرت سیگنالِ متفاوت جمع‌آوری کنم. بعد از جمع‌آوری تعداد زیادی (اما نه خیلی زیاد) از این نقاط کالیبراسیون، می‌خواهم برنامه‌ای بنویسم که ۴ سطح قدرت سیگنالِ وای‌فای را بگیرد و موقعیتی را به‌صورت یک بیضی خطا تخمین بزند. ممکن است سیگنال‌ها با دستگاهی متفاوت از دستگاهی که برای جمع‌آوری نقاط کالیبراسیون اولیه استفاده شده، اندازه‌گیری شوند. باید از چه الگوریتمی استفاده کنم؟ نمی‌خواهم با پرسیدن اینکه آیا می‌توانم وارد شوم و مکان دقیق روترشان را بررسی کنم، مزاحم همسایه‌هایم شوم. بااین‌حال، می‌توانم فرض کنم که مکان روترهای همسایه‌هایم تغییر نمی‌کند.

پاسخ‌ها (2)

۲۸ بهمن ۱۴۰۴، ۱۱:۲۴
به نظر می‌رسد که مکان سیگنال‌ها را خوب نمی‌دانید، بنابراین ابتدا باید آن‌ها را تخمین بزنید و سپس با داشتنِ آن تخمین‌ها، موقعیت خود را مثلث‌سازی کنید.
اگر دقت و واقع‌گرایی می‌خواهید، اتخاذ یک مدل احتمال‌پذیری (likelihood) برای قدرت سیگنال‌ها، یافتنِ حداکثر احتمال (maximum likelihood) و ساختنِ نقشه‌ی شبکه‌ای از احتمال موقعیت که از تخمین‌های حداکثر احتمال محاسبه می‌شود را در نظر بگیرید. ماکزیمم سراسری روی شبکه، بهترین تخمینِ موقعیت را مشخص می‌کند و خطوط تراز (نسبت به ماکزیمم) مجموعه‌های اطمینان را برای آن موقعیت به دست می‌دهند. یک مدل احتمال‌پذیری عمومی با فرض یک فرمول برای تضعیف سیگنال و در نظر گرفتنِ خطا به دست می‌آید. با یک فرمول کاملاً عمومی (با تابع تضعیف وابسته به زاویه و مکان) زیاد پیش نخواهید رفت، پس باید ساده‌سازی کنید. برای مثال، می‌توانید یک تابع تضعیف «سراسری» به نام f در نظر بگیرید، به طوری که اگر قدرت منبع در مکان وای‌فای x برابر با a باشد، قدرتِ مورد انتظار در مکان دیگر y به‌صورت زیر به دست آید z(y; x) = a f(d) که در آن d فاصله‌ی بین y و x است. برای مثال، می‌توانید تضعیفِ نسبتِ معکوسِ مربع را در نظر بگیرید که برای آن f(d) = 1 بر d^2 است، به شرطی که فاصله‌ی d از یک آستانه‌ی کوچک بزرگ‌تر باشد. به‌عنوان ساده‌سازی دیگر، می‌توانید فرض کنید قرائت قدرت z(y;x) در مکان y برای منبع x با یک خطای دارای توزیع نرمال از مقدارِ مورد انتظار اختلاف دارد؛ فرض کنید همه‌ی خطاها مستقل‌اند و همگی انحراف معیار یکسانی (s) دارند. سهم یک قرائت قدرت z در لگ‌احتمال (log likelihood) آن‌گاه به‌صورت زیر می‌شود L(y,x) = -[ (z(y;x) - a f(d))^2 بر s^2 + ln(s) ] بر ۲ لگ‌احتمالی که باید بیشینه شود، جمعِ دوگانه‌ی L(y,x) روی همه‌ی مکان‌های y و همه‌ی منابع x است. این تابعی از مکان‌های ناشناخته، شدت‌های منبعِ ناشناخته و انحراف معیارِ ناشناخته‌ی خطاهاست. یافتنِ انحراف معیارِ بهینه و شدت‌های منبعِ بهینه ساده است (مشتق‌های جزئی را بگیرید، صفر قرار دهید و حل کنید)، اما برای توابع تضعیفِ واقع‌گرایانه‌ی f شما با مسئله‌ای غیرخطی برای یافتنِ مکان‌ها روبه‌رو هستید. بااین‌حال، در مثال شما فقط ۱۳ پارامتر در میان است، بنابراین باید بتوانید آن را در مثلاً یک بهینه‌ساز چندمتغیره‌ی نیوتن–رافسون بریزید و به‌سرعت به پاسخ خوبی برسید. (ادبیات آماری پر از روش‌هایی برای حل این نوع معادلات است.) اگر علاوه بر آن فرض کنید دستگاه دوم به‌طور متناسب حساسیت بیشتری نسبت به دستگاهِ جمع‌آوری داده دارد، در مدلی که من پیشنهاد کرده‌ام تفاوت چندانی ایجاد نمی‌کند (زیرا قدرت سیگنال‌ها به‌صورت ضربی وارد می‌شوند). در واقع، اگر اجازه دهید خطاها با شدت مقیاس شوند (به طوری که انحراف معیارشان a ضرب در s باشد به‌جای s)، اختلاف بین دستگاه‌ها باید بی‌اهمیت باشد. برای ساده نگه‌داشتن این موضوع از برخی نکات ظریف آماری صرف‌نظر کرده‌ام، مانند این واقعیت که این یک مسئله‌ی بازه‌ی پیش‌بینیِ چندمتغیره است، نه یک مسئله‌ی بازه‌ی اطمینان. اگر مقدار خطا زیاد نباشد (یعنی s کوچک باشد)، این اختلاف چندان مهم نخواهد بود.