انتخاب زیر مجموعه بهینه ماهواره‌ها با استفاده از مدل ترکیبی SVMPSO به منظور افزایش دقت مکان‌یابی GPS

نوع مقاله: مقاله علمی فارسی

نویسندگان

1 استادیار، دانشکده مهندسی برق و کامپیوتر- دانشگاه تربیت دبیر شهید رجایی- تهران- ایران

2 - کارشناس ارشد، دانشکده مهندسی برق وکامپیوتر- دانشگاه تربیت دبیر شهید رجایی - تهران- ایران

3 دانشجوی کارشناسی ارشد، دانشکده مهندسی برق وکامپیوتر- دانشگاه شهید بهشتی - تهران- ایران

چکیده

هندسه ماهواره‌ها، نشان‌دهنده مکان‌های هندسی ماهواره‌های GPS است، فاکتوری که ارتباط هندسی صورت فلکی ماهواره‌های GPS را با همدیگر نشان می‌دهد، GDOP است. همه گیرنده‌ها از الگوریتم‌هایی برای انتخاب ماهواره‌ها استفاده می‌کنند، در این مقاله هدف استفاده از راهکار دسته‌بندی و تخمین فاکتور GDOP برای انتخاب زیر مجموعه بهینه ماهواره‌ها است. برای این منظور از مدل ترکیبی SVMPSO استفاده شده است. این مدل بر خلاف روش ماتریس معکوس که به دلیل تاخیرهای محاسباتی اعلام موقعیت بلادرنگ را دچار نقصان می‌کرد، با دقت، سرعت و قابلیت اطمینان بالا فاکتور GDOP را محاسبه می‌کند. مدل SVM یکی از مدل‌های قوی برای دسته‌بندی و تخمین است، نقش PSO بهینه‌سازی پارامترهای اساسی SVM است. این روش عملکرد SVM را در دقت و سرعت بهبود می‌دهد. مدل SVMPSO برای دسته‌بندی ماهواره‌های دیده شده با گیرنده‌ ارزان قیمت GPS پیاده‌سازی شد. 4 نقشه متفاوت برای محاسبه فاکتور GDOP وجود دارد. شبیه‌سازی هر 4 نقشه در این مقاله منعکس و با یکدیگر مقایسه گردید. پیاده‌سازی مدل و نتایج شبیه‌سازی خطای تخمین مدل SVMPSO را کمتر از 16/0 و دقت دسته‌بندی آن را بیش از 99 درصد نشان دادند. روش ارائه شده با روش‌های GA، NN و SVM که اخیرا برای محاسبه GDOP استفاده شده‌اند، مقایسه گردید.

کلیدواژه‌ها


عنوان مقاله [English]

Best Subset Selection of GPS Satellites Using Hybrid PSOSVM Algorithm to Increase Positioning Accuracy

نویسندگان [English]

  • Mohammad Hossein Refan 1
  • Adel Dameshghi 2
  • Mehrnoosh Kamarzarrin 3
1 Shahid Rajaee Teacher Training University
2 Shahid Rajaee Teacher Training University
3 Shahid Beheshti University
چکیده [English]

satellites as seen by the receiver(s), plays a very important role in the total positioning accuracy. Geometric Dilution of Precision (GDOP) is an indicator showing how well the constellation of GPS satellites is organized geometrically. The approach is based on approximation or classification of the GDOP factors utilizing the hybrid Particle Swarm Optimization (PSO) and Support Vector Machine (SVM) method. Without matrix inversion required, this method is capable of evaluating all subsets of satellites and hence reduces the computational burden. This would enable the use of a high-integrity navigation solution without the delay required for many matrix inversions. This method which are using the first time for classification of GDOP, were compared Neural Network (NN), Genetic Algorithm (GA), and SVM that recently been used for this purpose. The experiments show that the approximation total RMS errors of PSOSVM are less than 0.166m and total performance classification of PSOSVM is 99.9%.

کلیدواژه‌ها [English]

  • : Global Positioning System
  • Geometric Dilution of Precision
  • Support Vector Machine
  • Particle Swarm Optimization

سامانه مکان‏یاب جهانی یک نوع سامانه مسیریابی بر اساس ماهواره‏هاست‏ که توسط سازمان دفاعی آمریکا در دهه 1970 گسترش پیدا کرد [1]. سامانه GPS شامل بیش از 24 ماهواره است، با استفاده از حداقل 4 ماهواره مکان کاربر در 3 بعد مشخص می‏‏شود‏ [2]. در دقت مکان‏یابی GPS 2 عامل مؤثر‏ است؛ 1- خطای مشاهده شده در هر سیگنال دریافتی و 2- شکل هندسی تشکیل شده از ماهواره‏های قابل مشاهده. ‏عامل GDOP یک عامل هندسی از پیش تعیین شده است که اثر هندسه را در توصیف رابطه خطای اندازه‏گیری با خطا تعیین موقعیت نشان می‏دهد. در دسترس بودن ماهواره‏های GPS و پیکربندی آن‏ها نیز نقش مهمی در کنار عوامل دیگر بازی می‏کند [3]. برخی از گیرنده‏ها محدودیت‏هایی در تعداد ماهواره‏‏های قابل مشاهده دارند، بنابراین، نیاز است زیر مجموعه‏ای از ماهواره‏ها انتخاب شود. این زیر مجموعه باید بهترین یا قابل قبول‏ترین فرم هندسی را داشته باشند. بهینه‏ترین زیر مجموعه ماهواره‏ها با حداقل رساندن ‏عامل GDOP انتخاب می‏شود. گیرنده‏های GPS به علت تعداد محدود کانال‏هایشان قادر به پردازش داده‏های همه ماهواره‏های در دسترس نیستند، بنابراین، در این موارد انتخاب زیرمجموعه‏ای از ماهواره‏ها که بهترین یا مناسب‏ترین راه حل را عرضه می‏کنند، ضروری است‏ [1]. روش‏های موجود برای محاسبه GDOP بیشتر شامل روش‏های ماتریس معکوس، الگوریتم شکل‏دهی مسدود و مقدار حداکثر چهار وجهی است. درست‏ترین روش برای محاسبه GDOP، استفاده از ماتریس معکوس برای کلیه ترکیب‏ها و انتخاب کوچک‏ترین آن‏هاست، اما معکوس کردن ماتریس، به ویژه در زمانی که تعداد ماهواره‏ها زیاد است، بار محاسباتی زیادی برای پردازشگر ناوبر به همراه خواهد داشت [4]. از آنجا که GDOP یک تفسیر ساده را از دقت موقعیت توسط یک واحد از خطای اندازه‏گیری فراهم می‏کند، مطلوب است در صورت فلکی ماهواره‏ای ترکیبی از ماهواره را انتخاب کنید که کوچک‏ترین GDOP ممکن را داشته باشد. روش‏های گوناگونی بر اساس GDOP برای افزایش دقت مکان‏یابی GPS مطرح شده‏اند. به جای محاسبه مستقیم روابط GDOP و جلوگیری از زمان پردازش ماتریس معکوس به‏تازگی از روش‏های شبکه عصبی، الگوریتم ژنتیک و SVM استفاده شده است [7-5]. استفاده از مدل ماشین‏بردار پشتیبان در سال‏های اخیر برای دسته‏بندی و تخمین‏ گسترش یافته است، اما کاربردهای این مدل محدود شده است؛ زیرا کیفیت آن به تعیین شاخص‏های SVM و شاخص‏های کرنل SVM وابستگی زیادی دارد. نیاز است یک روش خودکار، معتبر و با سرعت نسبی زیاد برای تعیین شاخص‏ها انتخاب شود. در این مقاله، از روش PSO برای تعیین شاخص‏های SVM استفاده شده است. الگوریتم PSO روش‏ جستجوی مبتنی بر جمعیت است که بستگی به اشتراک‏گذاری اطلاعات میان اعضای جمعیت خود دارد، تا فرآیندهای جستجوی خود را با استفاده از ترکیبی از قوانین قطعی و احتمالی ارتقاءدهد. با این حال، PSO اپراتورهای ژنتیکی مانند آمیزش و جهش را ندارد. در مقایسه با GA نحوه به اشتراک‏گذاری اطلاعات درPSO متفاوت است. همچنین، زمان محاسباتی PSO و تعداد شاخص‏های مورد استفاده در این مدل نسبت به GA کمتر است. ساختار این مقاله به این شکل است؛ در بخش دوم مروری روی کارهای انجام شده درباره دسته‏بندی ماهواره‏ها انجام شده است. بخش سوم مقاله نحوه محاسبه GDOP را بیان می‏کند. بخش چهارم مقاله روش SVMPSO است. بخش پنجم شبیه‏سازی و بررسی‏ نتایج است. مقاله با نتیجه‏گیری در بخش ششم پایان می‏یابد.

2- مروری بر کارهای گذشته
این بخش به طور مختصر کارهای انجام شده در باره دسته‏بندی و تخمین ‏عامل GDOP را بیان می‏کند. از شبکه عصبی مصنوعی، Simon و همکارانش برای تخمین GDOP استفاده کردند [8]. یک سری از فعالیت‏های پژوهشی روی انواع شبکه‏های عصبی را Jwo برای این منظور انجام داد [4]. مبنای شبکه عصبی حداقل‏سازی ریسک ساختاری است، این امر بیشتر موجب کاهش تعمیم‏پذیری خواهد شد. همچنین، این مدل بیشتر موجب افزایش زمان آموزش و تعیین شاخص‏های ساختار شبکه خواهد شد. روش دیگر برای تقریب ضریب GDOP استفاده از SVR بود که توسط Wu و همکارانش ارایه‏ شد [7]. این روش بر خلاف روش شبکه عصبی از ریسک ساختاری بهره می‏برد. وقتی که از این مدل‏ها استفاده می‏شود تعیین ساختار ANN، تعیین وزن‏ها و بهینه‏سازی وزن‏ها، تعیین نوع تابع کرنل SVM و انتخاب گام به گام شاخص‏های آزاد آن همواره مسأله است. در روش SVR از جستجو هدایت شده برای تعیین شاخص‏های SVM استفاده شده است. دکتر موسوی روش ACOA را برای این منظور استفاده کرد [9] که بدون استفاده از ماتریس معکوس تمام زیر مجموعه ماهواره‏ها را محاسبه کرده و پیچیدگی محاسباتی را کاهش می‏دهد. الگوریتم ژنتیک نیز توسط موسوی برای این منظور ارایه‏ شد [10]. سرعت این روش بالا بود و در مقایسه با شبکه عصبی روش سریع‏تر و دقیتری در شبیه‏سازی‏ها نشان داده است. استفاده از محاسبات تکاملی توسط رنجبر و همکارانش به‏تازگی در زمینه تخمین GDOP ارایه‏ شده است [11].

3- ‏عامل GDOP
شکل (1) ارتباط بین ماهواره‏ها، مرکز زمین و کابران مکان‏یابی را مشخص می‏کند. در این شکل بردار نشان‏دهنده ارتباط بین مرکز زمین با یک ماهواره است. بردار نشان‏دهنده ارتباط از مرکز زمین به کاربر است. همچنین، بردار نشان دهنده ارتباط از کاربر به ماهواره است [12]. ارتباط بین این بردارها با معادله (1) توصیف می‏شود:
(1)
فاصله از طریق زمان انتشار سیگنال مابین ماهواره تا گیرنده GPS کاربر تعیین می‏شود. شبه فاصله GPS برای هر ماهواره مطابق با رابطه (2) است.
(2)

در این معادله، و به ترتیب نشان دهند مکان کاربر و مکان ماهواره در سه بعد هستند. شاخص‏ C نشان دهنده سرعت نور و نشان‏دهنده نویز اندازه‏گیری شبه‏فاصله است.

شکل (1): ارتباط بین ماهواره، گیرنده مرکز زمین

با تعریف و با توجه به رابطه (2) خواهیم داشت:
(3)

در رابطه (3) ، ، و برقرار است. بردار نشان‏دهنده بردار line-of-sight از کاربر به ماهواره است. رابطه (3) به شکل زیر بازنویسی می‏شود:
(4)

راه حل کوچک‏ترین مجذور برای معادله شبه فاصله خطی GPS، (معادله 4) به شکل زیر ارایه‏ شده است:
(5)

در معادله (4) ابعاد ماتریس هندسی G است که در آن خواهد بود. کیفیت راه حل ناوبری برای معادله شبه فاصله خطی با به دست آوردن تفاوت موقعیت‏های صحیح و تقریبی به شکل معادله (6) است:
(6)

در رابطه اخیر و متوسط صفر دارند. کوواریانس بین خطاها در اجزای موقعیت تخمین زده شده برابر است با:
(7)

که در آن عملگر امید ریاضی است‏. اگر تمام اجزای Vدو به دو ناهمبسته و واریانس داشته باشند. بنابراین، و در نتیجه:
(8)

بهترین حالت هندسی ماهواره‏ها وقتی حاصل می‏شود که ماهواره‏ها با حداکثر فاصله از هم در فضا قرار گرفته باشند. تأثیرهای هندسی ماهواره‏ها با یک عدد تک بعدی به نام DOP اندازه‏گیری و تعریف می‏شود. هر چه مقدار این عامل کمتر باشد وضعیت هندسی بهتری حاصل خواهد شد. تغییرات نسبی ماهواره‏ها و گیرنده‏ها موجب تغییر مقدار DOP خواهد شد. تغییر DOP بیشتر جز دو مورد به کندی است، وقتی که ماهواره از دید گیرنده خارج شود و وقتی که بین ماهواره و گیرنده موانع وجود داشته باشد [12]. با توجه به نیاز کاربر انواع مختلفی از DOP وجود دارد، ترکیب DOP مکان با DOP زمانی DOP هندسی را شکل می‏دهد [9]. در این مورد ماتریس G به شکل رابطه (9) تعریف می‏شود:
(9)

جایی که و به ترتیب ارتفاع و زاویه ماهواره است. ‏عامل GDOP از رابطه زیر حاصل می‏شود:
(10)

این ‏عامل مشخص می‏کند که چقدر یک واحد از خطای اندازه‏گیری در خطای موقعیت برای نقطه‏ای با مختصات مشخص دخیل است. تعیین دقیق ماهواره‏ها بر اساس ضریب GDOP به دقت بیشتر در مکان‏یابی منجر می‏شود. از آنجا که یک ماتریس می‏باشد و دارای 4 مقدار ویژه به ازای است، مشخص است که 4 مقدار ویژه ماتریس خواهد بود. براساس این واقعیت رابطه (2) به شکل زیر بازنویسی می‏شود:
(11)

بر اساس ارتباط بین ورودی و خروجی 4 نقشه برای GDOP قابل اجرا است. جدول (1) و شکل (2) این 4 نقشه را مشخص می‏کند.

جدول (1): ساختار 4 نقشه محاسبه ‏عامل GDOP
نقشه ارتباط تعداد ورودی تعداد خروجی
1
4 4
2
10 4
3
4 1
4
10 1

نگاشت با تعریف 4 متغیر به شکل زیر انجام می‏شود [12].
(12)
(13)
(14)
(15)

چهار نقشه مختلف به این شکل است که:
نقشه اول، چهار ورودی و چهار خروجی:
(16)
(17)

نقشه دوم، 10 ورودی و 4 خروجی:
(18)
(19)

نقشه سوم، 4 ورودی و 1 خروجی:
(20)
(21)

نقشه چهارم، 10 ورودی و 1 خروجی:
(22)
(23)

نگاشت بهGDOP بسیار غیر خطی است و به شکل تحلیلی حل نمی‏شود. تعیین آن با مدل SVMPSO و با آزمایش هر 4 نقشه انجام می‏شود [6]، [9]، [10].


شکل (2): ارتباطات برای 4 نقشه محاسبه GDOP

4- ماشین بردار پشتیبان
یکی از پرکاربردترین دسته‏بندی‏کننده‏ها، که برای نخستین بار در سال 1992 ارایه‏ شد، ماشین بردار پشتیبان است. این مدل توسط Vapnic و Cortes ارایه‏ شده است. این مدل در مواجه با نمونه‏های آموزشی محدود عملکرد مناسبی دارد و نسبت به مدل‏های مشابه دارای قدرت تعمیم‏پذیری بالایی است. در این مدل از اصول کمینه‏سازی ریسک ساختاری استفاده شده ‏است، در حالی که سایر روش‏ها از اصول کمینه‏سازی ریسک تجربی بهره می‏‏برند. ثابت شده است که ریسک ساختاری عملکرد بهتری نسبت به ریسک تجربی دارد [13]. مدل SVM نوع خاصی از مدل‏های خطی را می‏یابد که حداکثر حاشیه ابر صفحه را حاصل می‏کند [14]. حداکثر کردن حاشیه ابر صفحه به حداکثر شدن تفکیک بین طبقات منجر و به نزدیک‏ترین نقاط آموزشی بردارهای پشتیبان اطلاق می‏‏شود‏. تنها از این بردارها (نقاط) برای مشخص کردن مرز بین طبقات استفاده می‏شود. اگر نقاط آموزشی به شکل و بردار ورودی و ارزش طبقه تعریف شود، آنگاه در حالتی که داده‏ها به شکل خطی قابل تفکیک هستند، قواعد تصمیم‏گیری که تعریف می‏شود، به شکل معادله زیر است:
(24)

که در آن y خروجی معادله، ارزش طبقه نمونه آموزشی و . نشان‏دهنده ضرب داخلی است. بردار نشان دهنده یک داده ورودی و بردارهای ، بردارهای پشتیبان هستند. در معادله (24)، شاخص‏های و تعیین‏کننده ابر صفحه هستند. اگر داده‏ها به شکل خطی قابل تفکیک نباشند، معادله (24) به معادله زیر تغییر پیدا می‏کند:
(25)

تابع ، تابع کرنل است. در این مقاله، از تابع کرنل RBF استفاده شده است:
(26)

که در آن پهنای باند کرنل تابع پایه شعاعی است و و شاخص‏های تابع زیگمویدی هستند به نحوی که نامعادله برقرار باشد. فرآیند یادگیری برای ایجاد توابع تصمیم‏گیری دارای ساختاری دو لایه است. با استفاده از تئوری بهینه‏سازی برای طبقه‏بندی و بر اساس تئوری یادگیری آماری، SVM خطای طبقه‏بندی را به حداقل می‏رساند [19]، [20].

4-1- مدل رگرسیونی SVM
در ابتدا از SVM فقط برای دسته‏بندی استفاده می‏شد اما بعدها از این مدل در عملیات رگرسیونی نیز بهره گرفته شد [15]. مسأله رگرسیون در SVM یک تابع خطی به شکل است. این تابع بر روی یک مجموعه شامل نمونه مانند می‏تواند مقدار خروجی را بر مبنای مقادیر ورودی‏ تخمین بزند. در رابطه یاد شده x بردار مقادیر ورودی است. شاخص‏های w و b نیز شاخص‏های کنترل تابع هستند. نشان‏گر ضرب داخلی است‏. برای حل مسأله رگرسیون تابع تلفات Vapnik که در آن حداقل خطایی به میزان قابل صرف‏نظر کردن است، در نظر گرفته می‏شود. تابع تلفات به شکل زیر تعریف می‏شود [21]:
(27)

معرف تابع تلفات و میزان خطای مجاز در تابع تلفات است‏. شاخص‏های کنترل کننده تابع رگرسیون بهینه با حل مسأله بهینه‏سازی زیر حاصل می‏شوند [22]:
(28)
(29)
(30)

در روابط بالا متغیرهای slack هستند. این متغیرها به همراه تابع تلفات در شکل (3) نشان داده شده‏اند. برای حل مسأله بهینه‏سازی بالا به کمک تئوری لاگرانژ، تابع لاگرانژ مطابق با رابطه (31) نوشته می‏شود.
(31)

با بیشینه شدن تابع فوق تحت محدودیت‏های زیر، مقادیر بدست می‏آیند.
(32)

مسأله بهینه‏سازی بالا به کمک روش‏های QP قابل حل است‏. داده‏هایی که ضرایب لاگرانژ متناظر با آن‏ها غیر صفر باشد، به عنوان بردار پشتیبان شناخته می‏شوند [23]. از نظر هندسی این داده‏ها دارای خطاهای پیش‏بینی بزرگتر از هستند، بنابراین، بردارهای پشتیبان در درون باند قرار نمی‏گیرند، پس مقدار تعداد بردارهای پشتیبان را کنترل می‏کند [24]. به کمک ضرایب لاگرانژ و بردارهای پشتیبان، شاخص‏های کنترل کننده پاسخ بهینه نیز به شکل (23) تا (35) محاسبه می‏شوند [25]:

شکل (3): تابع تلفات Vapnik و متغیرهای slack [24]

(33)
(34)
(35)

در روابط بالا ، دو بردار پشتیبان هستند. برای ساخت مدل ماشین بردار پشتیبان، شاخص‏های C و توسط کاربر تعریف می‏شوند. شاخص‏ نیز می‏تواند مقادیر صفر تا بی‏نهایت را بپذیرد. مسأله رگرسیون خطی در SVM به آسانی قابل گسترش به رگرسیون غیر خطی است. بدین منظور از توابع کرنل استفاده می‏شود. بدین ترتیب در حالت رگرسیون غیر خطی در SVM شاخص‏های کنترل کننده تابع بهینه با روابط زیر محاسبه می‏شوند [25]:
(36)
(37)

در روابط بالا K نشان دهنده کرنل است.

4-2- بیان مسأله
مدل SVM دارای یک اشکال است که استفاده از آن را در محیط‏های پژوهشی و صنعتی محدود کرده است [16]. کیفیت واقعی الگوریتم SVM وابستگی کاملی به تنظیم ‏عامل‏های آن و همچنین، شاخص‏های کرنل دارد. بنابراین، بسیار ضروری است از روشی سریع، واقعی و خودکار برای بهینه‏سازی شاخص‏های SVM استفاده شده و از خطای تعمیم SVM کاسته شود [17]. انتخاب کمتر از مقدار درستC باعث عدم تعادل بین ریسک ساختاری و ریسک تجربی می‏شود. کم بودن بر روی ساختار مدل اثر‏گذار است و زیاد بودن آن باعث کاهش عملکرد است. اگر مقدار شاخص‏ کم باشد SVM با انباشتگی اطلاعات ورودی مواجه خواهد شد و اگر زیاد باشد SVM انعطاف لازم را برای حل مسائل پیچیده نخواهد داشت [18].وقتی از یک روش جستجو هدایت شده استفاده شود یا باید محدوده شاخص‏های جستجو افزایش یابد و یا این‏که باید اندازه گام‏های جستجو برای افزایش دقت و پیدا کردن راه حل مطلوب افزایش یابد. این امر باعث کاهش قابلیت اطمینان و افزایش زمان می‏‏شود‏.

4-3- روش بهینه‏سازی گروهی ذرات
از PSO برای رسیدن به ساختار بهینه SVM به شکل خودکار استفاده می‏شود، روش PSO، یک روش بهینه‏سازی است که از رفتار جمعی پرندگان در پیدا کردن غذا الهام گرفته شده است. در این روش هر نامزد برای جواب مسأله، یک پرنده در فضای جستجو است که ذره نام دارد. هر ذره دارای یک مقدار شایستگی است که توسط تابع شایستگی مسأله به دست می‏آید. پرنده‏ای که به غذا نزدیک‏تر است شایستگی بیشتری دارد [26]. این روش مانند بیشتر روش‏های جستجو با یک گروه از جواب‏های تصادفی جستجو را به شکل موازی شروع می‏کند و سپس، برای یافتن جواب بهینه در فضای مسأله با به هنگام کردن مکان ذره‏ها به جستجو ادامه می‏دهد. در روش بهینه‏سازی گروه ذرات برای هر ذره ، یک موقعیت و یک سرعت در نظر گرفته می‏شود. اگر بعد مسأله بهینه‏سازی n فرض شود، بردار موقعیت و بردار سرعت به شکل زیر است [37]:
(38)
(39)

که در آن و به ترتیب معرف موقعیت مکانی و سرعت بعد dام ذره i است. سرعت و موقعیت این بعد ذره در تکرار به شکل روابط (40) و (41) است.
(40)
(41)

در روابط بالا، وزن اینرسی در بازه [1,0]، و ضرایب یادگیری یا شتاب در بازه [2,1] هستند. را شاخص‏ اجتماعی و را شاخص‏ شناختی می‏گویند و معمولا این دو با هم برابر هستند. Rand عدد تصادفی با توزیع یکنواخت در بازه [1,0]، بهترین موقعیت ذره در بعد dام تاکنون و بهترین موقعیت در بین کل ذره‏ها برای بعد ام تاکنون و بهترین موقعیت ذره در بین کل ذره‏ها برای بعد dام تا به حال است. برای ایجاد توازن لازم بین یافتن پاسخ کلی و محلی در رابطه بالا وارد شده است. ثابت شده است که شرط همگرایی الگوریتم آن است که رابطه (42) برقرار باشد.
(42)
که در آن و هستند. برای جلوگیری از واگرایی الگوریتم، معمولا مقدار نهایی سرعت هر ذره به یک مقدار بیشینه محدود می‏شود. یعنی . شرط خاتمه الگوریتم همگرایی آن یا توقف بعد از تعداد معینی تکرار است. شایستگی هر ذره با استفاده از تابع برازندگی، ، سنجیده می‏شود. این تابع برازندگی مربوط به مسأله مورد نظر بوده و هدف کمینه کردن آن است. بهترین موقعیت هر ذره iام در هر تکرار طبق رابطه (43) به هنگام می‏شود:
(43)

این رابطه به این معناست که اگر مقدار فعلی تابع برازندگی ذره iام، به ازای موقعیت فعلی ، از برازنده‏ترین مقدار قبلی آن کمتر باشد، همین موقعیت به عنوان بهترین موقعیت این ذره ثبت می‏شود و در غیر این صورت بهترین موقعیت ذره، بهترین موقعیت قبلی باقی خواهد ماند [28]. فلوچارت الگوریتم PSO در شکل (4) دیده می‏شود. هر ذره دارای یک مکان تصادفی با فضای D بعدی و سرعت تصادفی در هر بعد است، هر ذره مورد ارزیابی قرار می‏گیرد، اگر ارزیابی هر ذره بهتر از بهترین ارزش ذرات بود، بردار مکان برای هر ذره ذخیره شود. اگر ارزش ذره در ارزیابی بهتر از بهترین کلی ذرات بود بردار مکان برای بهترین کلی ذخیره شود. سرعت و مکان ذره تا تصدیق شرایط پایانی به روز می‏شود. برای الگوریتم PSO 30 ذره به طور تصادفی تولید شد‏. ضرایب و به ترتیب 3/2 و 8/1 تعیین شد‏ و وزن اینرسی به طور خطی بین 9/0 تا 5/0 کاهش پیدا کرد. حداکثر تعداد نمونه‏ها 200 انتخاب شد. مقادیر شاخص‏ c جستجو شده بین 01/0 و 35000 است، در حالی‏که مقدار شاخص‏ بین 0001/0 و 32 بوده است. مدل PSO برای تعیین شاخص‏های SVM به شکل شکل (5) استفاده شد [29]:

5- پیاده‏سازی و شبیه‏سازی
5-1- پیاده‏سازی
به منظور نشان دادن کیفیت و حسن عملکرد مدل SVMPSO در دسته‏بندی و تخمین مقادیر GDOP، آزمایش‏هایی طراحی شد. از یک گیرنده GPS مدل U-blox LEA-6H برای جمع‏آوری اطلاعات استفاده شد‏. از ویژگی‏های بارز این گیرنده 50 کاناله بودن، قابلیت ردیابی 16 ماهواره به طور همزمان و دقت مکان‏یابی 5 متر است. در شکل (6) تصویر گیرنده همراه با برد جانبی که قابلیت اتصال به درگاه‏های USB و RS232 را دارد نشان داده شده است. از درگاه سریال برای ارتباط با نرم‏افزار MATLAB استفاده می‏شود. این گیرنده با استفاده از USB به کامپیوتر شخصی متصل می‏شود [30]. اطلاعات در آزمایشگاه GPS دانشگاه تربیت دبیر شهید رجایی جمع‏آوری شده‏است. مختصات دقیق نقطه‏ای که گیرنده GPS در آن مکان قرار گرفته و نمونه‏برداری انجام شده به شکل زیر است:

با توجه به اینکه تغییر ‏عامل GDOP به کندی است و برای تغییر آن باید ترکیب ماهواره دچار تغییر شود و این مستلزم حرکت آن‏ها و قرار‏گیری آن‏ها در مکان مناسب به لحاظ هندسی است، زمان دریافت اطلاعات گیرنده روی 1 دقیقه تنظیم شد. اطلاعات ورودی مربوط به محاسبات GDOP در پیام Satellite Status پروتکل UBX گیرنده U-blox قرار دارد، اطلاعات مهم این پیام که برای پیاده‏سازی مدل ضروری است در جدول (2) نشان داده شده است. این اطلاعات مطابق با ساختار این پیام با استفاده از نرم‏افزار MATLAB رمزگشایی، تجزیه شده و سپس، مطابق با روابط بخش 3 به عنوان ورودی مدل PSOSVM برای تقریب مقادیر دقیق GDOP در چهار نوع مختلف استفاده شد، مدل PSOSVM نیز مقادیر GDOP را تقریب می‏زند. مقادیر GDOP که توسط الگوریتم داخلی گیرنده محاسبه می‏شود در پیام NAV-DOP پروتکل UBX گیرنده قرار دارد، نرم‏افزار MATLAB این اطلاعات را نیز با فرمان که از طریق درگاه سریال گیرنده به آن اعمال می‏شود دریافت می‏کند و با مقادیر محاسبه شده با مدل PSOSVM مقایسه شد.


شکل (4): ساختار الگوریتم PSO


شکل (5): ساختار مدل PSOSVM


جدول (2): پیام اطلاعات ماهواره‏ها
ساختار پیام سرآغاز طول پیام
0xF1 0x03 5 + 6*GT
مکان توضیح
0 شناسه پروتکل
1 شناسه پیام
2 تعداد ماهواره تحت دید (n)
3+6n. شناسه ماهواره
4+6n. وضعیت ماهواره
5+6n. زوایه ماهواره
6+6n. ارتفاع ماهواره

شکل (7) گراف هندسی ماهواره‏های GPS را که توسط گیرنده GPS انتخاب شده است، برای3000 نمونه نشان می‏دهد. شبیه‏سازی با استفاده از یک پردازنده انجام شده است.


شکل (6): گیرنده GPS U-blox LEA-6H


شکل (7): گراف هندسی ماهواره‏های GPS

5-2- آزمایش‏ها
به طور کلی دو راهکار برای تعیین هندسه‏ ماهواره بر مبنای GDOP وجود دارد: روش دسته‏بندی و روش تخمین.
دسته‏بندی GDOP برای انتخاب یک زیر مجموعه قابل انتخاب ( که ‏عامل GDOP به اندازه کافی کوچک باشد) از ماهواره‏ها انجام می‏شود. تقریب GDOP محاسبه این ‏عامل از روی اطلاعات وردی گیرنده GPS و مطابق با چهار نقشه تشریح شده است.

5-2-1- بررسی عملکرد مدل در تقریب GDOP
عملکرد تقریب GDOP مدل استفاده شده با استفاده از شاخص‏های جدول (3) بررسی شد. هدف اصلی، مقایسه 4 نقشه مختلف محاسبه GDOP با یکدیگر و همچنین، سنجش کارایی مدل SVMPSO و مقایسه آن با سایر مدل‏هایی است که به‏تازگی به این منظور استفاده شده‏اند. در این شاخص‏ها متغیر ، ‏عاملGDOP حاصل شده از ماتریس معکوس و مقدار ‏عامل GDOP خروجی مدل PSOSVM است. در این شاخص‏ها متغیر n، تعداد داده‏های آزمون را نشان می‏دهد.

جدول (3): معیارهای مورد استفاده در سنجش عملکرد مدل PSOSVM در تخمین مقادیر GDOP
Title Equation
Mean Square Error(MSE)
Mean Absolute Error(MAE)
Root Mean Square Error(RMSE)
Mean Absolute Percentage Error(MAPE)

در شکل (8)، GDOP محاسبه شده با ماتریس معکوس با رنگ قهوه‏ای و مقادیر GDOP محاسبه شده با نقطه‏های مشکی نشان داده شده است. مدل استفاده ‏شده در این شبیه‏سازی، نقشه نوع 1 محاسبه ضریب GDOP است. در قسمت (ب) همین شکل، شبیه‏سازی نقشه نوع دوم محاسبه GDOP آمده است که GDOP محاسبه شده با مدل PSOSVM، با نقاط بنفش مشخص شده است. به ترتیب در همین شکل و در قسمت‏های (ج) و (د) نقشه‏های نوع‏ سوم و چهارم محاسبه GDOP با نقاط رنگی سبز و آبی نمایان شده‏اند. به منظور مقایسه GDOP محاسبه شده در هر 4 نوع با یکدیگر و روش ماتریس معکوس شبیه‏سازی، شکل (6) قسمت (ه) منعکس شده است. شایان ذکر است که هر نوع، دارای پیچیدگی خاصی است، به گونه‏ای که نقشه‏های نوع 1 و 3 از شاخص‏های کمتری نسبت به نوع 2 و 4 بهره می‏برند، زیرا در نوع 1 و 3 از 4 ورودی استفاده می‏شود در حالی که در نوع 2 و 4 از 10 ورودی بهره می‏برد. تفاوت نوع 2 و 4 در این است که ورودی‏ها در نوع 4 مستقیم و در نوع 2 غیر مستقیم‏اند که موجب می‏شود تعداد شاخص‏های نوع 4 از نوع 2 کمتر شود. نتیجه‏ای که حاصل می‏شود این است که در نقشه چهارم بین ورودی و خروجی‏ها ارتباط آسان‏تری برقرار است. خطای محاسبه GDOP با استفاده از رابطه زیر به دست می‏آید:
(44)

در شکل (9) خطای محاسبه GDOP توسط مدل SVMPSO و در نوع‏های 1، 2، 3 و 4 به ترتیب به رنگ‏های مشکی، سبز، بنفش و آبی نشان داده شده است. به منظور بررسی خطای محاسبه در شکل (9) قسمت (ه) ، خطا‏های محاسبه این 4 نوع با هم مقایسه شده‏اند. مطابق با این شکل خطای حاصل از نقشه نوع سوم کمتر و پایدارتر از سایر نقشه‏‏هاست. نقشه نوع سوم برای محاسبه مستقیم GDOP مناسب‏تر است. نقشه‏های 4 ورودی، نوع 1 و نوع 3، عملکرد بهتری نسبت به نقشه‏های 10 ورودی، نوع 2 و 4، دارند. با توجه به شکل 9-ه خطای نوع سوم از 3 نقشه دیگر کمتر است. جدول (4) دقت مدل PSOSVM را بر اساس معیارهای سنجش تعریف شده نشان می‏دهد. از این جدول مشخص است که دقت نقشه نوع سوم بهتر از سایر نقشه‏هاست و پس از آن نقشه نوع اول دارای بهترین دقت است. عملکرد نقشه‏ی نوع چهارم نسبت به سایر نقشه‏ها ضعیف‏تر بوده است. مقایسه مدل PSOSVM با سایر مدل‏هایی که برای تخمین GDOP استفاده شده‏اند در جدول (4) نشان داده شده است. با توجه به شاخص‏های تعریف شده‏ اساسی برای مدل SVR، بهترین دقت حاصل شده برای این مدل که برای نوع سوم و با 4 ورودی است تقریبا 4/0 است‏. این مدل با مدل‏های دیگر شامل مدل NN، GA نیز مقایسه شد. مدل GA نیز نسبت به سه مدل دیگر دارای سرعت بهتری است و نسبت به NN دقیق‏تر است. مدل SVM تعمیم‏پذیری بهتری نسبت به GA و NN دارد. اما روش SVM چون از جستجوی هدایت شده و غیر خوکار استفاده می‏کند دقت کمتری نسبت به PSOSVM دارد. در مدل PSOSVM بین سرعت و دقت توازن برقرار است.

جدول (4): مقایسه روش PSOSVM با مدل GA، NN و SVM به لحاظ سرعت و دقت
نقشه 4 نقشه 3 نقشه 2 نقشه 1 معیار
45/0 13/0 14/0 17/0 MAE
17 6 11 7 MAPE
29/0 02/0 03/0 05/0 MSE
538/0 188/0 345/0 226/0 STD
021/0- 027/0 056/0 039/0- MEAN
0018/0 0 0 00004/0 MIN
57/1 67/0 05/1 01/1- MAX
538/0 166/0 362/0 229/0 RMS

 


(الف) (ب)

(ج) (د)

(ه)
شکل (8): تخمین GDOP با روش SVMPSO و مقایسه با روش ماتریس معکوس
الف- محاسبه با نقشه اول ب- محاسبه نقشه دوم ج- محاسبه با نقشه سوم د- محاسبه با نقشه چهارم



(الف) (ب)

(ج) (د)

(ه)
شکل (9): خطای تخمین GDOP با مدل SVMPSO
الف- خطای محاسبه با نوع اول ب- خطای محاسبه نوع دوم ج- خطای محاسبه با نوع سوم د- خطای محاسبه با نوع چهارم


جدول (5): بررسی آماری خطای تخمین GDOP
شاخص‏ NN GA SVM PSOSVM
RMSE 502/0 283/0 403/0 166/0
CPU (s) 029/0 010/0 014/0 066/0

5-3-1- بررسی عملکرد دسته‏بندی GDOP با استفاده از مدل PSOSVM
مقدار DOP اگر کمتر از 2 باشد عالی است. این مقدار نیازمند آنتنی قوی است تا گیرنده بتواند ماهواره‏ها را به خوبی ببیند. مقدار DOP بین 2 تا 3 بسیار خوب است. اگر مقدار DOP از 6 بیشتر شود مکان‏یابی بسیار ضعیف و غیر قابل اطمینان می‏شود. جدول (6) نرخ DOP را برای حالات مختلف نشان می‏دهد. دسته‏بندی GDOP به منظور انتخاب یک و تنها یک زیر مجموعه‏ی مناسب است. دسته‏بندی با 5 بردار مشخص به شکل [00001]، [00010]، [00100]، [01000]، [10000] که به ترتیب نشان دهنده سطح عالی، خوب، متوسط، کمابیش ضعیف و ضعیف می‏باشد تعریف شده است. از معیار CE برای بررسی عملکرد دسته‏بندی استفاده شده است. از جدول (7) مشخص است که درصد کل CE 5 است. این مدل دارای خطای بسیار کمی است و مدل بسیار خوبی برای دسته‏بندی به حساب می‏آید. دقت مدل با شاخص‏ CA به شکل زیر محاسبه می‏شود:
(45)
جدول (6): نرخ DOP
DOP Value binary coding نرخ شماره کلاس
2<g<=0 00001 عالی 1
3<g<=2 00010 خوب 2
4<g<=3 00100 معتدل 3
5<g<=4 01000 متوسط 4
5> 10000 ضعیف 5

جدول (7): نتایج دسته‏بندی GDOP با روش GASVM
Cluster 1 2 3 4 5 Total CE
Exc 327 0 0 0 0 327 0%
Good 0 824 0 0 0 824 0%
Mod 0 1 198 0 0 199 5/0%
Fair 0 0 0 82 0 82 0%
Poor 0 0 0 0 68 68 0%
دقت مدل PSOSVM 95/99 درصد است. این مدل را با مدل‏ SVM که از PSO بی‏بهره است مقایسه کردیم. همچنین، مدل PSOSVM با مدل GA و NN که پیش از این استفاده شده است مقایسه شد‏. نتایج این بررسی در جدول (8) منعکس شده است. مطابق با این بررسی مدل ارایه‏ شده بهترین دقت را داراست. پس از آن، مدل GA از دقت خوبی برخوردار است.

جدول(8): مقایسه مدل PSOSVM با مدل‏های GA، NN و SVM
PSOSVM NN GA SVM الگوریتم
9/99 91 6/99 4/98 CA

6- نتیجه ‏گیری
به منظور بهبود عملکرد دقت گیرنده‏های GPS به‏ویژه گیرنده‏های ارزان قیمت کمینه‏سازی ضریب GDOP اهمیت فراوانی دارد. از میان همه‏‏ ماهواره‏هایی که گیرنده می‏بیند، یک دسته از ماهواره‏ها، که بهترین حالت همدوسی را دارد باید انتخاب ‏شود‏ تا ضریب GDOP کم شود. در این مقاله، از روش PSOSVM برای مدل‏سازی GDOP استفاده شده است. در مقایسه با GA، NN و SVM مدل یاد شده دقیق‏تر و سریع‏تر است. عملکرد تخمین‏زنی و دسته‏بندی این مدل کامل و بسیار مؤثر‏ بود. دقت دسته‏بندی مدل 9/99 درصد و دقت مدل در تقریب مقادیر GDOP کمتر از 16/0 بود.

 

[1]  Indriyatmoko, A., Kang, T., Lee, T. Y, J., Jee G. I., Cho, Y. B., Kim, J., “Artificial Neural Networks for Predicting DGPS Carrier Phase and Pseudo-Range Correction”, Journal of GPS Solutions; Vol. 12, No. 4, pp. 237-247, 2008.

[2]  Zhang, J., Zhang, K., Grenfell, R., Deakin R., “GPS satellite velocity and acceleration determination using the broadcast ephemeris”, Journal of Navigation; Vol. 59, pp. 293–305, 2006.

[3]  Jwo, D. J., “ Efficient DOP calculation for GPS with and without altimeter aiding”, This Journal; Vol. 54, No. 2, pp. 269-279, 2001.

[4]  Jwo, D. J., Lai, C. C., “Neural network-based GPS GDOP approximation and classification”, Journal of GPS Solutions; Vol. 11, No. 1, pp. 51–60, 2007.

[5]  Wu, C. H., Ho, Y. W., Chen, L. W., Huang, Y. D., “Discovering approximate expressions of GPS geometric dilution of precision are using genetic programming”, Advances in Engineering Software; Vol. 45, pp. 332–340, 2012.

[6]  Mosavi, M. R., Azami, H., “Applying Neural Network for Clustering of GPS Satellites”, Journal of Geoinformatics; Vol. 7, No. 3, pp. 7-14, 2011.

[7]  Wu, C. H., Su, W. H., Ho, Y. W., “A study on GPS GDOP approximation using support vector machines. IEEE Trans Instrum Meas; Vol. 60, No. 1, pp. 137–45, 2011.

[8]  Simon, D., Sherief, H., “Navigation satellite selection using neural networks”, Neuron computing; Vol. 7, No. 1, pp. 247–58, 1995.

[9]  Mosavi, M. R., “An Effective Method for GPS GDOP Clustering Using Ant Colony Optimization Algorithm”, Asian Journal of Geoinformatics; Vol. 10, No. 4, pp. 91-97, 2010.

[10]    Mosavi, M. R., “Applying Genetic Algorithm to Fast and Precise Selection of GPS Satellites”, Asian Journal of Applied Sciences; Vol. 4, No. 3, pp. 229-237, 2011.

[11]    Ranjbar, M., Mosavi, M. R., “Simulated Annealing Clustering for Optimum GPS Satellite Selection”, IJCSI International Journal of Computer Science Issues; Vol. 9, No. 3, pp. 100-104, 2012.

[12]   Jwo, D. J., Chin, K. P., “Applying Back-propagation Neural Networks to GDOP Approximation”, journal of navigation; Vol. 55, No. pp. 97-108, 2002.

[13]   Vapnik, V. N., Golowich, S. E., Smola, A. J., “Support vector machine for function approximation, regression estimation and signal procession”, Adv. Neural Information Procession Syst; Vol. 9, No. 9, pp. 281-287, 1995.

[14]   Cao, L. J., Tay, F. E. H., “ Support vector machine with adaptive parameters in financial time series forecasting”, IEEE Transactions on Neural Network; Vol. 14, No. 6, pp. 1506–1518, 2003.

[15]   Farag, A., Refaat, M. M., Regression Using Support Vector Machines: Basic Foundations. Technical Report. [Online]. Available:http://wenku.baidu.com/view/256be2ef0975f4 6526d3e107.html

[16]   Minqiang, P., Dehuai, Z., Gang, X. u., “Temperature Prediction of Hydrogen producing reactor using SVM regression with PSO-SVM”, Journal of computers; Vol. 5, No. 3, pp. 388-393, 2010.

[17]   Nizam, M., Mohamed. A., Al-Dabbagh, M., Hussain. A. “Using Support Vector Machine for Prediction Dynamic Voltage Collapse in an Actual Power System”, International Journal of Electrical and Electronics Engineering; Vol. 37, No. 5, pp. 3730-3736, 2009.

[18]   Shuo, H., Rung-Ching, C., “Using SVM with Financial Statement Analysis for Prediction of Stocks. Communications of the IIMA; Vol. 7, No. 4, pp. 63-72, 2007.

[19]   Mohandes, M. A., Halawani, T. O., Rehman. S., Hussain, A. A., “Support vector machines for wind speed prediction”, Renewable Energy; Vol. 29, Vol. 6, pp. 939–947, 2004.

[20]   Radhika, Y., Shashi, M., “Atmospheric Temperature Prediction using Support Vector Machines”, International Journal of Computer Theory and Engineering; Vol. 1, No, 1, pp. 1793-8201, 2009.

[21]   Burgers, C. J. C., “A tutorial on support vector machines for pattern recognition” Data Mining and Knowledge Discovery; Vo. 21, No. 3, pp. 121–167, 1999.

[22]    Cao, L. J., Tay, F. E. H., “Support vector machine with adaptive parameters in financial time series forecasting”, IEEE Transactions on Neural Network’ Vol. 14, No. 6, pp. 1506–1518, 2003.

[23]    Ganapathiraju, A., “Support vector machines for speech recognition”, PhD Thesis, Mississippi State University, USA, 2001.

[24]    Drucker, H., Burges, C., Kaufman, L., Smola, A., Vapnik, V., “Support Vector Regression Machines”, MIT Press, Cambridge; Vol. 9, No. 3, pp. 155-161, 1997.

[25]    Smola, A. J., Scolkopf, B., “Tuotorial on support vector regression, NeuroCOLT2 technical report series”, NC2-TR-1998-03, 1998.

[26]   Lin, S. W., Ying, K. C., Chen, S. C., Lee, Z. J., “Particle swarm optimization for parameter determination and feature selection of support vector machines”, Expert Systems with Applications, Vol. 35, pp. 1817–1824, 2008.

[27]   Ren, Y., Bai, G., “Determination of Optimal SVM Parameters by Using GA/PSO”, Journal of computers; Vol. 5, No. 8, pp. 1160-1168, 2010.

[28]   Ardjani, F., Sadouni, K., “Optimization of SVM Multiclass by Particle Swarm (PSO-SVM)”, I. J. Modern Education and Computer Science; Vol. 2, No. 2, pp. 32-38, 2010.

[29]   Shih-Wei, L., Kuo-Ching, Y., Shih-Chieh C., Zne-Jung, L., “Particle swarm optimization for parameter determination and feature selection of support vector machines”, Expert Systems with Applications; Vol. 35, No. 4, pp. 1817-1824, 2008.