سیف اله سلیمانی

یکی از مفیدترین پیشرفت های فنّاوری تعیین موقعیت مکانی افراد است که بسیار کارآمد بوده و برنامه های بسیاری نیز برای کار با آن طراحی شده اند. در مبحث مکان یابی دو حوزه کاملاً متفاوت وجود دارد، یکی مکان یابی در فضاهای باز و دیگری مکان یابی در فضاهای سرپوشیده. منظور از فضاهای سرپوشیده مکان ها و ساختمان های سربسته ای است که سیگنال های سیستم موقعیت یاب جهانی نمی توانند به داخل آن ها نفوذ کنند. در فضاهای باز عمل تعیین مکان کاربر از طریق GPS انجام می شود. امکان دسترسی زیاد به دستگاه تلفن همراه و افزایش تقاضای سرویس دهی مبتنی بر مکان منجر به گسترش سیستم های مکان یابی شده است. با توجه به پیشرفت های مخابرات بی سیم، فناوری WiFi روش هایی مبتنی بر قدرت سیگنال دریافت شده ارائه کرده است که گزینه ی جذابی برای مکان یابی داخلی خواهد بود. سیستم های مکان یابی اثرانگشت به دلیل هزینه توسعه پایین و دقت مکان یابی زیاد، توجه محققان زیادی را به خود جلب کرده است. در ساختمان های بزرگ مانند بیمارستان ها، فرودگاه ها و موزه ها تنوع اطلاعات و همچنین حجم اطلاعات ورودی برای انجام فرایند مکان یابی بسیار زیاد است. در این ساختمان ها به این دلیل که فضای مسئله خیلی بزرگ است، مجموعه اثرانگشت جمع آوری شده بسیار زیاد می باشد که مکان یابی در این فضاها نیازمند صرف وقت و هزینه ی بالایی است و این در حالی است که دستگاه های قابل تحرک مانند تلفن همراه توان پردازشی و حافظه پایینی دارند، بنابراین کاهش سربارهای پردازشی برای یافتن موقعیت یک فرد، موضوع ارزشمندی است؛ پس تا جایی که امکان دارد باید ورودی های مسئله را محدود کرد تا در مدت زمان معقولی مکان یابی انجام شود. برای این منظور روش مکان یابی مبتنی بر درخت kd ارائه شده است. ازآنجاکه خاصیت درخت شکستن فضا است و ایده کلی درخت kd تقسیم فضا به چندین زیرفضا با استفاده از نقاط موجود در صفحه می باشد، هدف این است که به کمک درخت kd فضای جستجو را شکسته و در یک فضای محدودتر مکان یابی را انجام داد. روش پیشنهادی به این صورت است که ابتدا با استفاده از یکی از الگوریتم های خوشه بندی مشخص شود که فضای موردبررسی به چند زیرفضا قابل تقسیم است، سپس ایده الگوریتم درخت kd را مطابق با ورودی های مسئله که RSS های اثرانگشت در هر نقطه می باشد، اصلاح کرده و الگوریتمی برای ایجاد درخت kd پیشنهاد می شو