ردگيری هدف به صورت توزيعشده با استفاده از الگوريتم اجماع به ميانگين مشاهدات در شبکه حسگری
محورهای موضوعی : مهندسی برق و کامپیوترايمان مقصودلو 1 , میثم رئیس دانائی 2 , حميد آرزومند 3
1 - دانشگاه جامع امام حسین (ع)
2 - دانشگاه جامع امام حسین (ع)
3 - دانشگاه جامع امام حسین (ع)
کلید واژه: ردگيری هدف, شبکه حسگری, فيلتر ذرهاي توزيعشده, مسئله اجماع به میانگین,
چکیده مقاله :
در اين مقاله، الگوریتم نوینی جهت کاهش شدید سربار مخابراتی در ردگيری توزيعشده (غیرمتمرکز) برای تکهدف در يک شبکه حسگری بیسیم ارائه گردیده است. این الگوریتم مبتني بر نگاه نوینی به حل مسئله اجماع به ميانگين و استفاده از فيلترهای ذرهای بهصورت توزيعشده است. در الگوريتم ارائهشده در این مقاله، بر عکس الگوریتمهای متداول که برای ردگیری توزيعشده جهت محاسبه وزن ذرات در فيلترهای ذرهای به حل مسئله اجماع به ميانگين برای تقریب تابع شبیهنمایی سراسری میپردازند، مدل جديدی براي مشاهده بر مبنای تقریب گوسی ارائه میشود که تنها در حل مسئله اجماع به ميانگين بر روی مشاهدات دریافتی گرهها در شبکه (و نه برای تقریب توابع شبیهنمایی سراسری) به کار گرفته میشود. این نوآوریها موجب کاهش قابل توجه ردوبدلشدن اطلاعات مابین گرههای شبکه و در نتیجه مصرف بسیار اندک منابع انرژی میگردد. در سناریوهای مختلف، کارايي الگوريتم پيشنهادی با الگوريتم متمرکز و الگوريتم توزيعشده مبتني بر گراف، مقايسه گردیده و نتايج شبيهسازی بیانگر آن هستند که با استفاده از این ایده، در ازای افت قابل قبول دقت ردگیری، سربار مخابراتی شبکه به شدت کاهش مییابد.
In this paper, a new algorithm is presented to drastically reduce communication overhead in distributed (decentralized) single target tracking in a wireless sensor network. This algorithm is based on a new approach to solving the average consensus problem and the use of distributed particle filters. For the algorithm of this paper, unlike the common algorithms that solve an average consensus problem just to approximate the global likelihood function to calculate the particle importance weights in distributed tracking, a new model for observation is presented based on the Gaussian approximation, which only solves the problem Consensus is applied to the mean on the received observations of the nodes in the network (and not to approximate the global likelihood function). These innovations significantly reduce the exchange of information between network nodes and as a result uses much less energy resources. In different scenarios, the efficiency of the proposed algorithm has been compared with the centralized algorithm and the distributed algorithm based on the graph, and the simulation results show that the communication overhead of the network is greatly reduced in exchange for an acceptable drop in tracking accuracy by using our proposed algorithm.
[1] Z. Ying and L. Gao, "Sensor-networked underwater target tracking based on grubbs criterion and improved particle filter algorithm," IEEE Access, vol. 7pp. 142894-142906, 2019.
[2] Z. Hao, Z. Xue, W. Zhuping, Y. Huaicheng, and S. Jian, "Adaptive consensus-based distributed target tracking, with dynamic cluster in sensor networks," IEEE Trans. on Cybernetics, vol. 5, no. 5, pp. 1580-1591, May 2018.
[3] R. Jesse, K. Achutegui, and J. Miguez, "A distributed particle filter for nonlinear tracking in wireless sensor networks," Signal Processing, vol. 98, pp. 121-134, May 2014.
[4] F. Zhao and L. Guibas, Wireless Sensor Networks: An Information Processing Approach, Morgan Kaufmann, San Francisco, CA, USA, 2004.
[5] W. Zhao and Y. Liang, "Energy-efficient and robust in-network inference in wireless sensor networks," IEEE Trans. on Cybernetics, vol. 45, no. 10, pp. 2105-2118, Oct. 2015.
[6] O. Hlinka, F. Hlawatsch, and P. Djuric, "Distributed particle filtering in agent networks: a survey, classification, and comparison," IEEE Signal Processing Magazine, vol. 30, no. 1, pp. 61-81, Jan. 2012.
[7] L. Xiao and S. Boyd, "Fast linear iterations for distributed averaging," Syst. Contr. Lett., vol. 53, no. 1, pp. 65-78, Sept. 2004.
[8] S. Farahmand, S. I. Roumeliotis, and G. B. Giannakis, "Set-membership constrained particle filter: distributed adaptation for sensor networks," IEEE Trans. Signal Processing, vol. 59, no. 9, pp. 4122-4138, Sept. 2011.
[9] D. Gu, J. Sun, Z. Hu, and H. Li, "Consensus based distributed particle filter in sensor networks," in Proc. Int. Conf. Inform. Automationpp. 302-307, Changsha, China, 20-23 Aug. 2008.
[10] Y. Xu, K. Xu, J. Wan, Z. Xiong, and Y. Li, "Maneuvering target tracking by using particle filter," in Proc. IEEE Joint 9th IFSA World Congress and 20th NAFIPS Int. Conf., pp. 2223-2228, Vancouver, Canada, 25-28 Jul. 2002.
[11] O. Hlinka, O. Sluciak, F. Hlawatsch, P. Djuric, and M. Rupp, "Likelihood consensus and its application to distributed particle filtering," IEEE Trans. on Signal Processing, vol. 60, no. 8, pp. 4334-4349, Aug. 2012.
[12] J. Y. Yu, M. J. Coates, and M. G. Rabbat, "Graph-based compression for distributed particle filters," IEEE Trans. on Signal and Information Processing over Networks, vol. 5, no. 3, pp. 404-417, Sept. 2019.
[13] A. Mohammadi and A. Asif, "Distributed consensus + innovation particle filtering for bearing/range, tracking with communication constraints," IEEE Trans. on Signal Processing, vol. 63, no. 3, pp. 620-635, Feb. 2014.
نشریه مهندسی برق و مهندسی کامپیوتر ایران، ب- مهندسی کامپیوتر، سال 21، شماره 1، بهار 1402 67
مقاله پژوهشی
ردگيري هدف به صورت توزيعشده با استفاده از الگوريتم اجماع
به ميانگين مشاهدات در شبکه حسگري
ايمان مقصودلو، ميثم رئيسدانايي و حميد آرزومند
چکیده: در اين مقاله، الگوریتم نوینی جهت کاهش شدید سربار مخابراتی در ردگيري توزيعشده (غیرمتمرکز) برای تکهدف در يک شبکه حسگري بیسیم ارائه گردیده است. این الگوریتم مبتني بر نگاه نوینی به حل مسئله اجماع به ميانگين و استفاده از فيلترهاي ذرهاي بهصورت توزيعشده است. در الگوريتم ارائهشده در این مقاله، بر عکس الگوریتمهای متداول که برای ردگیری توزيعشده جهت محاسبه وزن ذرات در فيلترهاي ذرهاي به حل مسئله اجماع به ميانگين برای تقریب تابع شبیهنمایی سراسری میپردازند، مدل جديدي براي مشاهده بر مبنای تقریب گوسی ارائه میشود که تنها در حل مسئله اجماع به ميانگين بر روی مشاهدات دریافتی گرهها در شبکه (و نه برای تقریب توابع شبیهنمایی سراسری) به کار گرفته میشود. این نوآوریها موجب کاهش قابل توجه ردوبدلشدن اطلاعات مابین گرههای شبکه و در نتیجه مصرف بسیار اندک منابع انرژی میگردد. در سناریوهای مختلف، کارايي الگوريتم پيشنهادي با الگوريتم متمرکز و الگوريتم توزيعشده مبتني بر گراف، مقايسه گردیده و نتايج شبيهسازي بیانگر آن هستند که با استفاده از این ایده، در ازای افت قابل قبول دقت ردگیری، سربار مخابراتی شبکه به شدت کاهش مییابد.
کلیدواژه: ردگيري هدف، شبکه حسگري، فيلتر ذرهاي توزيعشده، مسئله اجماع به میانگین.
1- مقدمه
امروزه با پيشرفت تکنولوژي، شبکههاي حسگري بيسيم نيز که از سال 1990 معرفي شدهاند، با قابليتهاي توأم حسگري، پردازشي و مخابراتي در زمينههاي متنوعي بهکارگيري ميگردند [1]. تعدادي از اين زمينهها شامل سيستمهاي مراقبتي، اقدامات نجات، رهگيري هدف و حملونقل هوشمند ميباشند [2]. حسگرهاي مورد استفاده در اين شبکهها ميتوانند رادار، ليدار، حسگرهاي نوري و حرارتي باشند که مشاهداتی در فضای قطبی مانند فاصله از هدف و یا زاویه نسبی را اندازهگيري ميکنند [3]. در اينگونه شبکهها گرههاي شبکه در ناحيه مورد نظر توزيع ميگردند و بعد از اين که هر گره با کمک حسگرهاي خود، مشاهدهای از هدف دریافت میکند، با واحد پردازشگر درونی خود، مشاهدات را پردازش نموده و نتايج محاسبات را مستقیماً به یک گره مرکزی ارسال میکند (شبکههای حسگری متمرکز) و یا صرفاً از طريق لينک مخابراتي هر گره با گرههای همسايه، تبادل داده مینماید و هیچ گرهی، مسئول اطلاعات
و تصمیمگیری نهایی نمیباشد (شبکههای حسگری توزیعشده). مزیت شبکههای حسگری توزیعشده نسبت به متمرکز در مقاومبودن در برابر قطعي تعدادی از گرههای شبکه، هزينههاي مخابراتي و پردازشي کمتر [4] و داشتن قابلیت مقياسپذيري (قابلیت اضافهشدن بینهایت گره جدید به شبکه) ميباشد [5].
معماریهای متفاوتی برای ردگیری در شبکههای حسگری توزیعشده توسط فیلترهای ذرهای پیشنهاد گردیده است [6]. در این مقاله، جهت انجام ردگیری توزیعشده بر روی الگوریتمهای مبتنی بر حل مسئله اجماع به میانگین تمرکز میکنیم [7].
هر حسگر (هر گره) در شبکه، یک تخمین محلی را از تابع توزیع پسین هدف، نگهداری و پیامها را با حسگرهای همسایه در یک شبکه ارتباطی مبادله میکند. هدف این است که همه گرهها (مستقل از همدیگر) تابع توزیع پسین هدف را با ترکیب دادههای همه حسگرهای مربوط در شبکه محاسبه کنند. ایده سادهای که در این زمینه به ذهن میرسد این است که در هر گره و به ازای هر ذره از فیلتر ذرهای، یک بار مسئله اجماع به میانگین برای محاسبه تابع شبیهنمایی سراسری حل گردد. این ایده دارای سربار مخابراتی بسیار بالایی است. یک راه برای کاهش سربار مخابراتی، استفاده از ایده منطق فازی جهت شناسایی ذرات مؤثر در تخمین توزیع پسین است؛ در نتیجه برای ردوبدل کردن اطلاعات، تنها عده کمی از ذرات مورد استفاده واقع میشوند و این ايده، حجم محاسبات را کاهش میدهد [8].
راه حل بعدی این است که تابع توزیع پسین با یک توزیع گوسی ترکیبی تقریب زده شود و تنها پارامترهای این چندگوسی ردوبدل گردند [9]. در [10] به جای اجماع به پارمترهای توزیع گوسی ترکیبی از اجماع به میانگین آمارگان کافي توزیع پسین هدف جهت تخمین توزیعشده تابع توزیع پسین هدف استفاده شده است. روشی که اخیراً مورد توجه قرار گرفته است، محاسبه تابع شبیهنمایی سراسری تمامی ذرات بهصورت توزیعشده (در هر گره مستقل از گرههای دیگر) و با حل مسئله اجماع به میانگین است [11] و [12].
به طور مثال در [11]، لگاریتم تابع شبیهنمایی سراسری بر اساس تبدیل خطی توابع پایهای از قبل معلوم نوشته میشود. این توابع پایه برای تمامی گرهها از قبل معلوم هستند. هر گره، ضرایب این تبدیل خطی را طبق اصل کمترين مربعات خطا محاسبه کرده و این ضرایب با حل مسئله اجماع به میانگین در کل شبکه تجمیع میشوند.
در [12] از تئوری مبتني بر گراف جهت تقریب تابع شبیهنمایی سراسری با بسط به بردارهای پایه استفاده شده است. در روش اخير نياز است که مجموعه ذرات تولیدی فیلتر ذرهای در تمامی گرهها یکسان باشند (اصطلاحاً سنکرون باشند) تا بتوان وزنهای اهمیتی فیلتر ذرهای را در هر گره بدون در دسترس بودن مشاهدات تمامی گرهها بهصورتی یکسان محاسبه کرد. مسئله اصلی در این رهیافت، رسیدن به یک تعادل در نسبت سربار مخابراتی به کیفیت ردگیری توزیعشده است. به علاوه، محاسبه گرافهاي معادل ذرات و بردارهاي ويژه ماتريس لاپلاسين گراف نيز بسيار دشوار و زمانبر ميباشد. مثلاً [12] این تعادل را با کاهش تعداد توابع پایه مورد استفاده برقرار کرده است. در مقاله حاضر، جهت کاهش سربار مخابراتی از قید سنکرونبودن مجموعه ذرات صرف نظر کردهایم. به عبارت دیگر نیازی به تخمینزدن تابع شبیهنمایی سراسری به روش توزیعشده نیست و ردوبدلکردن ضرایب مربوط مابین گرهها جهت حل مسئله اجماع از گراف معادل ذرات به تنها دو پارامتر بردار مشاهده، تقلیل پیدا میکند؛ این امر موجب کاهش شدید سربار مخابراتی میشود. جهت انجام این کار، مدل جدیدی برای مشاهدات حاصل از حل مسئله اجماع به میانگین بهدست میآید که غیر خطی است. با بهکارگیری فیلتر کالمن توسعهیافته بر روی این مدل جدید میتوان آمارگان کافی را جهت ساختن تابع توزیع پیشنهادی مؤثر برای تولید ذرات فیلتر ذرهای محاسبه نمود.
ادامه مقاله به اين صورت تنظیم شده که ابتدا صورت مسئله ردگيري و ساختار گراف شبکه بيان ميگردد. سپس عملکرد الگوريتم پيشنهادي DEKPF طي 9 مرحله به صورت تئوري ارائه ميشود. در ادامه ميزان سربار مخابراتي و مصرف انرژي روش پيشنهادي مورد ارزيابي قرار گرفته و در قسمت شبيهسازي مونتکارلو الگوريتم پيشنهادي شبيهسازي و نتايج حاصل بررسي ميگردد. در انتها نيز نتيجهگيري و پیشنهادهایی در ارتباط با بهبود روش ارائه ميگردد.
2- بيان مسئله
شبکه حسگري که در اين مقاله مورد استفاده قرار گرفته است توسط يک گراف غيرجهتي ثابت مدل شده که در اين شبکه، گرهها ميتوانند توسط يک مدل غيرخطي از هدف، مشاهدات حاوي نويز دريافت نمايند. در اين شبکه حسگري، وجود يال بين دو رأس از گراف به معناي آن است که گرههاي معادل اين 2 رأس داراي ارتباط مخابراتي با يکديگر هستند. این شبکه، شامل گره ميباشد که در ناحيه مورد نظر پراکندهشده اين شبکه با گراف غيرجهتي مدل ميگردد. در اين گراف، مجموعه تمام گرههاي شبکه و مجموعه تمام يالهاي گراف است و رابطه بين اين 2 مجموعه برقرار ميباشد. دوتايي
در صورتي عضو مجموعه است که گره با گره از طريق لينک ارتباطي متصل باشد. مجموعه تمام همسايگان تکپرش گره را با نشان ميدهيم که در آن درجه گره ناميده ميشود. در هر گام زماني، هر گره باید پارامتر یا پارامترهایی را که تابعی از مشاهده آن هستند در تعداد تکرارهاي مشخص با گرههاي همسايه خود معاوضه نمايد. بردار حالت هدف که ميخواهيم در اين مسئله ردگيري نماييم در هر گام زماني بهصورت است که شامل موقعيت و سرعت هدف در مختصات دوبعدي ميباشد. مدل ديناميکي هدف در اين شبکه بهصورت رابطه زیر در نظر گرفته ميشود [13]
(1)
همچنين مشاهده انجامشده از هدف در گره و در گام زماني بهصورت (2) ميباشد
(2)
در (1) و (2)، حالت هدف و مشاهده انجامشده در گره از شبکه است. و بردارهاي نويز حالت و مشاهده بوده که به ترتيب داراي ماتريسهاي کواريانس و ميباشند. براي سادگي کار در محاسبات انجامشده در اين مقاله، ماتريسهاي کواريانس و کليه گرهها يکسان در نظر گرفته شدهاند. و به ترتيب برد و زاويه هدف نسبت به گره ميباشند و بردار مشاهده به صورت (3) تعريف ميگردد
(3)
در (3)، نويز است که به صورت گوسي با متوسط صفر و کواريانس
در نظر گرفته ميشود و و به صورت (4) و (5)
تعريف ميگردند
(4)
(5)
که و بهترتيب مختصات گره و هدف در دستگاه مختصات مرجع ميباشند. از آنجا که در (1) و (2)، تابع و داراي خاصيت غيرخطي زيادي هستند، فيلترهاي ذرهاي، انتخاب مناسبی براي ردگيري هدف در اين گونه محيطها ميباشند و به همین دلیل تمام مراجعی که در این مقاله مورد بررسی قرار گرفتهاند با استفاده از فیلتر ذرهای به ردگیری هدف به صورت توزیعشده میپردازند. در این مقاله تابع توزیع پیشنهادی فیلتر ذرهای به وسیله فیلتر کالمن توسعهیافته که بر روی مدل جدیدی از مشاهدات تعریف شده است، ساخته میشود. فيلتر کالمن توسعهيافته با تخمين اوليهاي از هدف، آمارگان مرتبه اول و دوم (یعنی بردار میانگین و ماتریس کواریانس) را در اختیار تابع توزیع پیشنهادی گوسی فیلتر ذرهای قرار میدهد تا ذرات فيلتر ذرهاي را تولید نماید. به همین دلیل روش ابداعگردیده در اين مقاله، فيلتر ذرهاي توزيعشده مبتنی بر فیلتر کالمن توسعهیافته 2(DEKPF) ناميده شده است. در يک نگاه کلي، الگوريتم DEKPF به صورت شماتيک در شکل 1 نشان داده شده است و همان طور که در اين شکل ديده ميشود، اين روش شامل 9 مرحله ميباشد.
3- تشريح عملکرد الگوريتم DEKPF
الگوريتم DEKPF روشي مبتني بر محاسبه مدل مشاهده جديد در هر گام زماني است. منظور از مشاهده جديد همان اجماع به ميانگين مشاهدات انجامشده در کل شبکه ميباشد که خروجي آن، مشاهدهاي است که از متوسطگيري مشاهدات تمام گرهها به دست آمده است. در اين الگوريتم و همان طور که در شکل 1 ديده ميشود، مشاهده کلي شبکه به عنوان مشاهده ورودي فيلترها در نظر گرفته شده که لازمه آن، استخراج مدل جديد و جايگزينکردن مدل مشاهده محلي نشان داده شده در (2) برای هر گره با مدل جديد ميباشد که در ادامه مراحل 9گانه الگوريتم DEKPF تشريح ميگردد.
[1] این مقاله در تاریخ 2 اسفند ماه 1400 دریافت و در تاریخ 1 آبان ماه 1401 بازنگری شد.
ايمان مقصودلو، دانشکده مهندسي برق، دانشگاه جامع امام حسین (ع)، تهران، ایران، (email: iman.maghsudlu@gmail.com).
میثم رئیسدانایی (نویسنده مسئول)، دانشکده مهندسي برق، دانشگاه جامع امام حسین (ع)، تهران، ایران، (email: mraeesdanaee@ihu.ac.ir).
حميد آرزومند، دانشکده مهندسي برق، دانشگاه جامع امام حسین (ع)، تهران، ایران، (email: arezumand.h@ihu.ac.ir).
[2] . Extended Kalman Filters-Based Distributed Particle Filters
شکل 1: شماتيک الگوريتم DEKPF.
شکل 2: دستگاههاي مختصات محلي و مرجع در شبکه حسگري.
3-1 مرحله اول
در مرحله اول که با در شکل 1 مشخص شده است، هر گره مشاهده خود را از هدف به صورت دريافت ميکند. همان طور که در قسمت قبلي توضيح داده شد، شامل برد و زاويه مشاهدهشده از هدف نسبت به گره ميباشد. در اين مرحله، هر گره زاويه و برد هدف را نسبت به موقعيت خود اندازهگيري ميکند و بنابراين موقعيت هدف در هر لحظه در هر گره به صورت متفاوت قرائت ميگردد.
3-2 مرحله دوم
در مرحله دوم که با در شکل 1 نشان داده شده است، ميبايست که مشاهدات انجامشده در تمام گرهها به دستگاه مشترکي به نام دستگاه مرجع تبديل گردد تا بتوان عمليات متوسطگيري را روي آنها پيادهسازي نمود. تبديل دستگاه مختصات محلي هر گره به دستگاه مختصات مرجع در شکل 2 نشان داده شده است. از شکل 2 ميتوان استفاده کرد و روابط تبديل مختصات محلي به مختصات مرجع را در گره مطابق (6) و (7) نوشت
(6)
(7)
بردار مختصات مشاهده گره در دستگاه مختصات مرجع در گام زماني k و مختصات هدف در دستگاه محلي گره است که منظور از اندیس ، محلیبودن مختصات میباشد.
3-3 مرحله سوم
در مرحله دوم، مشاهدات انجامشده در تمام گرههاي شبکه به دستگاه مختصات مرجع منتقل گردیده و بنابراين ميتوانند با هم در يک الگوريتم اجماع، متوسطگيري شوند. اين اجماع به میانگین در مرحله از شکل 1 انجام و خروجي آن ناميده شده و به صورت (8) محاسبه ميگردد
(8)
که مشاهده سراسري1 ناميده ميشود، حاوي اطلاعات ناشي از مشاهدات محلي تمام گرهها بوده و با توجه به اين که خروجي الگوريتم اجماع به میانگین ميباشد، در محل تمام گرهها در دسترس خواهد بود. نکته مهم در اينجا آن است که مشاهده سراسري بهدستآمده در اين مرحله در محل تمام گرهها جهت انجام عمل ردگيري به عنوان ورودي به فيلترهاي کالمن توسعهيافته وارد ميگردد. بنابراين قبل از اعمال اين مشاهده به فيلترهاي محلي بايد مدلي را که اين مشاهده از آن تبعيت ميکند، محاسبه نمود.
3-4 مرحله چهارم
همان طور که گفته شد، مشاهده جديد نياز به مدل جديدي دارد تا بتواند به عنوان ورودي مشاهده در فيلترهاي کالمن توسعهيافته مورد استفاده قرار گيرد. مدل مشاهده جديد که بايد جايگزين مدل مشاهده اوليه (2) گردد در مرحله و به صورت (9) در نظر گرفته ميشود
(9)
در رابطه بالا نويز مدل مشاهده جديد است که کواريانس آن ناميده ميشود. بنابراين در مرحله چهارم بايد رابطه بين و محاسبه گردد و از آنجايي که مطابق با (8) ترکيبي از مشاهدات محلي گرهها ميباشد، براي محاسبه (9) ميتوان ابتدا رابطه ميان تمام ها را با بهدست آورد و سپس با درنظرگرفتن اين روابط ميتوان رابطه نهايي را بين و محاسبه نمود. با توجه به (6) داريم
(10)
در (10) با فرض کوچکی نويز زاويه ميتوان فرض کرد و نيز و به ترتيب طول و عرض هدف در دستگاه مختصات محلي گره ميباشند. همچنين با فرض ميتوان نتيجه گرفت که و (10) را به صورت (11) بازنويسي نمود
(11)
ميدانيم که برابر طول هدف در دستگاه مختصات مرجع ميباشد و با جايگذاري در (11) ميتوان به (12) رسيد
(12)
در (12)، و نويزهاي مدل جديد هستند که بايد توزيع آنها مشخص گردد. فرض ميکنيم و داراي توزيع نرمال به ترتيب به صورت (13) و (14) باشند
(13)
(14)
با انتخاب و ، ابتدا توزيع را با استفاده از لم 1 با توزيع نرمال تقريب ميزنيم.
لم 1: اگر متغير تصادفي نرمال باشد، متغير تصادفي داراي توزيع تقريبي نرمال بهصورت (15) خواهد بود (اثبات آن به عهده خواننده گذاشته ميشود)
(15)
با استفاده از لم 1 ميتوان توزيع تقريبي نرمال را با اندکي محاسبات به صورت (16) محاسبه نمود
(16)
با کمک (16) و با درنظرداشتن اين که مقداری ثابت است ميتوان توزيع را بهصورت (17) محاسبه کرد
(17)
بعد از محاسبه توزيع جمله اول نويز در (12)، نوبت به محاسبه توزيع جمله دوم نويز ميرسد. با توجه به ثابتبودن مقدار و نيز دراختيارداشتن توزيع از (13) ميتوان توزيع را بهصورت (18) نوشت
(18)
با محاسبه توزيع و و فرض مستقلبودن آنها ميتوان توزيع نويز (12) را بهصورت (19) بهدست آورد
(19)
مشابه آنچه براي محاسبه گرديد ميتوان را نيز بهدست آورد. باتوجه به (7) ميتوان مقدار عرض مشاهدهشده در گره را در زمان در دستگاه مختصات مرجع بهصورت (20) نوشت
(20)
همچنین در (20) مانند آنچه در (10) ديديم با فرض کوچکبودن نويز زاويه، فرض شده و همچنين با فرض تساوي برقرار ميباشد. همچنين ميدانيم که برابر عرض هدف در دستگاه مختصات مرجع است که با جايگذاري در (20) به (21) ميرسيم
(21)
اگر و در نظر گرفته شود و محاسباتي مانند (16) تا (18) انجام گردد ميتوان نويز (21) را بهصورت (22) بهدست آورد
(22)
با فرض مستقلبودن و ، توزيع بردار نويز مشاهده محلي بهصورت رابطه زير ميباشد
(23)
مدل مشاهده جديد در محل گره بهصورت (24) بهدست ميآيد
(24)
در نهايت با توجه به (8) مدل مشاهده سراسري شبکه به صورت (25) محاسبه ميگردد
(25)
که در آن متوسط نويزهاي مشاهده محلي جديد در کل شبکه است که داراي توزيع تقريبي به صورت (26) ميباشد
(26)
اکنون (25) و (26) خروجيهاي مرحله چهارم هستند که براي ادامه کار، نتيجه به مرحله بعد ارسال ميگردد.
3-5 مرحله پنجم
يکي از قسمتهايي که خروجي مرحله چهارم را مورد استفاده قرار ميدهند فيلترهاي EKF هستند که در مرحله پنجم قرار گرفتهاند. از آنجايي که مشاهده جديد حاصل ترکيب مشاهدات کلي شبکه است، بنابراين خروجي فيلترهاي EKF در هر گره نيز اطلاعات ناشي از کل شبکه را در بر داشته و تخمين انجامشده در هر يک از فيلترها تخمين سراسري شبکه ميباشد. روابط مورد استفاده در فيلترهاي EKF مرحله پنجم به صورت زير هستند:
گام پيشبيني فيلتر EKF
(27)
جدول 1: مقايسه سربار مخابراتي و مصرف انرژي روش پیشنهادی DEKPF و مبتني بر گراف ( متناسب با سربار مخابراتی روش مبتنی بر گراف و متناسب با سربار مخابراتی روش DEKPF است).
| ||||
5/0 | 4/0 | 2/0 | 1/0 |
|
250 | 200 | 100 | 50 |
|
(28)
گام تصحيح فيلتر EKF
(29)
(30)
(31)
در (29) تا (31)، مقدار پيشبيني تخمين حالت و کواريانس اين پيشبيني در گره و زمان است. بهره فيلتر EKF، تخمين نهايي حالت و کواريانس تخمين حالت توسط فيلترهاي محلي EKF ميباشد.
3-6 مرحله ششم
در مرحله ششم، دومين اجماع به ميانگين بين خروجي فيلترهاي EKF گرههاي شبکه انجام ميگردد تا آمارگان مرتبه اول و دوم لازم برای تابع توزیع پیشنهادی بهصورت يکسان در محل تمام گرهها بهدست آيد. مقدار تخمين نهايي شبکه و کواريانس آن بهترتيب با و نشان داده ميشود که از (32) و (33) بهدست ميآيند
(32)
(33)
مرحله ششم به اين جهت در نظر گرفته شده تا با متوسطگيري تخمين گرههاي شبکه، آمارگان مرتبه اول و دوم لازم برای تابع توزیع پیشنهادی يکساني در اختيار گرهها جهت توليد ذرات قرار گيرد و از آنجايي که
در مرحله سوم، اولين اجماع به ميانگين بين مشاهدات گرهها انجام شده است، بنابراين خروجي فيلترهاي EKF در محل گرهها خيلي بههم نزديک هستند و ميتوان گفت که اجماع به ميانگين که در مرحله ششم صورت ميگيرد با تکرار بسيار کم ميتواند اجرا گردد. حتي در شرايطي که سرعت تخمين بيشتري مورد نياز باشد ميتوان مرحله ششم را از الگوريتم حذف نمود چون اجباري براي يکسانبودن آمارگان مرتبه اول و دوم لازم برای تابع توزیع پیشنهادی در اين الگوريتم وجود نداشته است.
3-7 مرحله هفتم و هشتم (پيادهسازي فيلتر ذرهاي توزيعشده)
تا اينجا با کمک روش اجماع به ميانگين مشاهدات گرهها، محاسبه مدل مشاهده جديد و بهکارگيري فيلترهاي EKF توانستهايم که آمارگان مرتبه اول و دوم لازم برای تابع توزیع پیشنهادی جهت توليد ذرات فيلترهاي ذرهاي محلي يعني و را محاسبه نماييم. فيلترهاي ذرهاي شامل ذراتي هستند که در مرحله هفتم توليد گردیده و وزن ذرات توليدشده نيز در مرحله هشتم محاسبه ميگردند. ذرات فيلترهاي ذرهاي بهصورت محلي در هر گره از توزيع پيشنهادي گوسي به صورت (34) بهدست ميآيند
(34)
نکتهاي که بايد در اين قسمت مورد توجه قرار گيرد اين است که چون مشاهدات تمام گرههاي شبکه در توليد اين ذرات نقش داشتهاند، بنابراين ذرات توليدشده در محتملترين ناحيه از تابع احتمال قرار ميگيرند که اين موضوع در بالارفتن دقت تخميني که از اين ذرات به دست ميآيد بسيار مؤثر خواهد بود. رابطهاي که در محاسبه وزن ذرات در فيلترهاي ذرهاي مورد استفاده قرار ميگيرد بهصورت (35) ميباشد
(35)
همان طور که در (35) ديده ميشود در محاسبه وزن ذرات نيز از مدل مشاهده جديد استفاده شده که اين سبب ميگردد تا اطلاعات موجود در تمام گرههاي شبکه در محاسبه وزن ذرات فيلتر ذرهاي مورد استفاده قرار گيرد و از اين رو ميزان دقت تخمين فيلتر نسبت به حالتي که تنها مشاهده يک گره در محاسبات استفاده ميگردد بسيار بالاتر خواهد بود. مدل مشاهده جديد که در (25) بهدست آمده است، براي محاسبه تابع احتمال سراسري جديد شبکه یا همان استفاده ميگردد و در الگوريتمهايي که در آنها مدل مشاهده جديد محاسبه نميشود، اين تابع احتمال بايد بهصورت توزيعشده در شبکه حسگري محاسبه گردد که نياز به سربار مخابراتي بالايي خواهد داشت.
3-8 مرحله نهم
بعد از محاسبه ذرات و وزن مربوط به آنها ميتوان در مرحله نهم با معيار کمينه ميانگين مربعات خطا (MMSE) مقدار تخمين و کواريانس آن را به صورت (36) و (37) بهدست آورد
(36)
(37)
4- تحليل سربار مخابراتي و انرژي مصرفي
ميزان سربار مخابراتي در روش DEKPF برابر با حاصلضرب تعداد تکرارهاي ناشي از اجماع به ميانگين در ابعاد بردار مشاهده است. در اينجا بردار مشاهده دوبعدي در نظر گرفته شده است. در روش مبتني بر گراف که در [12] معرفی گردیده است، مقدار سربار مخابراتي برابر با ضرب تعداد تکرارهاي اجماع به ميانگين و همچنین تعداد ذرات فیلتر ذرهای میباشد. هرچند که در این گونه روشها از تمامی اطلاعات استفاده نمیشود و با فشردهسازی مبتنی بر ساختاری که گراف ارائه میدهد، کسری از تعداد کل ذرات (که با ضریب نمایش داده میشود) را استفاده میکنند، مقدار حداقل یک دهم میباشد [12]. اگر ابعاد بردار مشاهده را (که در این مقاله برابر با دو است) و ابعاد بردار نمونهبرداری از تابع شبیهنمایی را در نظر بگيريم (که برابر با تعداد ذرات فیلتر ذرهای است)، نسبت سربار مخابراتي دو روش مذکور مطابق با جدول 1 ميباشد. نتایج جدول بيانگر کاهش قابل توجه سربار مخابراتي در روش پيشنهادي DEKPF نسبت به روش مبتنی بر گراف ميباشد. در اين جدول تعداد ذرات 1000 در نظر گرفته شده است.
شکل 3: شبکه حسگري و مسير حرکت هدف.
شکل 4: خروجي ردگيري متمرکز هدف در شبکه حسگري.
[1] . Global Observation
جدول 2: مزايا و معايب روشهاي DEKPF، متمرکز و مبتني بر گراف.
مصرف انرژي | سربار مخابراتي | دقت ردگيري | پارامتر روش | |
بسيار پايين | بسيار پايين | کمتر از روشهاي اجماع تابع احتمال | مقياسپذير | DEKPF |
بالا | بالا | بالا | مقياسپذير | Graph-base |
بالا در گرههاي نزديک مرکز | بالا در گرههاي نزديک مرکز | بالاتر از روشهاي توزيعشده | مقياسناپذير | CPF |
چون بيشتر انرژي مصرفي در يک شبکه حسگري ناشي از ميزان سربار مخابراتي در آن شبکه ميباشد، تحليل انرژي مصرفي نيز مشابه تحليل سربار مخابراتي و متناسب با دادههاي جدول 1 خواهد بود. همچنين در جدول 2، مزايا و معايب DEKPF همراه با ساير روشها آورده شده است. در اين جدول، روش مبتني بر گراف به نمايندگي از ساير روشهاي توزيعشده است که از اجماع به ميانگين برای محاسبه تابع شبیهنمایی سراسری بهره ميگيرند.
5- شبيهسازي مونتکارلو
در اين قسمت، الگوريتم اجماع به میانگین در مشاهدات را در محيط نرمافزاري Matlab و بر روي کامپيوتری با پردازنده 3Core i شبيهسازي ميکنيم تا بتوانيم ميزان کارايي اين الگوريتم را در مقايسه با الگوريتم متمرکز و الگوريتم مبتني بر گراف اندازهگيري نماييم. اين شبيهسازي
در يک شبکه حسگري شامل 20 گره پيادهسازي گردیده که اين گرهها بهصورت تصادفي در يک فضای مربعشکل با ابعاد پراکنده شدهاند. هر گره در اين شبکه تنها ميتواند با گرههاي همسايه با فاصله کمتر از m 12 مخابره مستقيم داشته باشد. شبکه توليدشده يک گراف متصل1 را تشکيل داده و تمام گرههاي شبکه، حداقل به يک گره ديگر از شبکه متصل هستند. مدل جنبشی در اين شبيهسازي به صورت (38) در نظر گرفته شده که يک حرکت داراي چرخش ثابت در جهت عقربههاي ساعت ميباشد [13]
(38)
یعنی بهنحوی که ماتريس که ماتريس دوران با بسامد زاویهای ثابت را در هدف ايجاد ميکند بهصورت (39) خواهد بود
(39)
شتاب ثابت هدف در اين شبيهسازي در نظر گرفته شده و نويز داراي کواريانس ميباشد. در اين شبيهسازي، عملکرد الگوريتم اجماع به ميانگين مشاهدات که در اين مقاله ارائه شده با عملکرد الگوريتم متمرکز و الگوريتم توزيعشده مبتني بر گراف مقايسه گردیده است. همان طور که در شکل 3 ديده ميشود، شبکه شامل گرهها و لينکهاي ارتباطي همراه با يک هدف شبيهسازي شده ميباشد که در آن مربعهاي توپر بيانگر گرهها هستند که با ساير گرههاي همسايه که در برد مخابراتي آنها هستند ارتباط دارند. منحني قرمز بيانگر مسير هدف است که بايد ردگيري گردد.
مشاهدات انجامشده در هر گره شامل فاصله هدف نسبت به گره مربوط و نيز زاويه هدف نسبت به همان گره ميباشد. مقدار واريانس مشاهده در اندازهگيري فاصله و مقدار واريانس مشاهده در اندازهگيري زاويه در نظر گرفته شده است. اين شبيهسازي براي تعداد 500 شبيهسازي مونتکارلو تکرار گردیده و خروجي ردگيري هر يک از الگوريتمهاي DEKPF، متمرکز و مبتني بر گراف بهدست آمده است. ابتدا خروجي الگوريتم متمرکز را در شکل 4 مشاهده ميکنيد.
در شکل 5 خروجي الگوريتمهاي DEKPF و مبتني بر گراف، نشان داده شده که ميزان دقت ردگيري روش پيشنهادي را با روشهاي اجماع به ميانگين تابع احتمال نشان ميدهد. براي اين که بتوانيم ميزان عملکرد اين الگوريتمها را بهصورت دقيق با هم مقايسه نماييم از پارامتر متوسط مربعات خطاي موقعيت2 بهصورت (40) استفاده شده است
شکل 5: خروجي ردگيري DEKPF هدف در شبکه حسگري.
جدول 3: مقدار RMSE روشهاي متمرکز، DEKPF
و مبتني بر گراف در تعدادي از گامهای زماني.
200 | 160 | 120 | 80 | 40 | Time (k) |
85/1 | 61/0 | 51/0 | 45/0 | 35/0 | DEKPF |
48/1 | 52/0 | 4/0 | 37/0 | 33/0 | Graph-based |
99/0 | 3/0 | 24/0 | 25/0 | 31/0 | CPF |
(40)
که تعداد شبيهسازي مونتکارلو و و به ترتيب مؤلفههاي محور طولي و عرضي تخمين هدف در گره ميباشند.
مقدار پارامتر RMSE شبيهسازي براي هر سه الگوريتم متمرکز، DEKPF و مبتني بر گراف در شکل 6 نشان داده شده است. همان طور که ديده ميشود، مقدار خطاي ردگيري در الگوريتم پيشنهادي DEKPF از روش مبتني بر گراف کمتر به نظر ميرسد؛ اما بايد دانست که ميزان سربار مخابراتي بسيار کاهش پيدا کرده که خود ميزان انرژي مصرفي در شبکه را تا حدود زيادي پايين ميآورد. براي اين که از نظر عددي اين مقادير قابل مقايسه باشند، مقدار RMSE در تعدادي از نقاط زماني در جدول 3 نشان داده شده است.
6- نتيجهگيري و کار آينده
در اين مقاله الگوريتم جديدي بر مبناي اجماع به میانگین مشاهدات در يک شبکه حسگري ارائه شده که در آن، بعد از اين که هر گره مشاهده را در گام زماني دريافت نمود، اجماع به میانگین بر روي مشاهدات گرهها صورت ميگيرد که نتیجه آن، ایجاد میانگینی از مشاهده تمامی گرههاي شبکه در دستگاه مختصات مرجع میباشد. با محاسبه مدل مشاهده جديد ميتوان در هر گره از فيلترهاي محلي (برای هر گره متفاوت از گره دیگر) از نوع فيلتر کالمن توسعهیافته بهره گرفت تا آمارگان مرتبه اول و دوم لازم برای تابع توزیع پیشنهادی گوسی جدیدی جهت توليد ذرات فيلتر ذرهاي را محاسبه نمود. حسن اين ایده در آن است که حل مسئله اجماع به میانگین تنها بر روی دو عضو بردار مشاهده صورت میگیرد که باعث کاهش شدید سربار مخابراتي به نسبت سایر روشهای ردگیری توزیعشده میگردد. این امر در کاهش مصرف انرژي گرههای شبکه نقشی مستقیم دارد و موجب افزایش طول عمر شبکه میگردد. البته هزینهای که پرداخت شده است، افت اندکی در دقت ردگیری نسبت به روشهاي متداول
شکل 6: RMSE در الگوريتم DEKPF (نمودار بالا)، الگوريتم مبتني بر گراف (نمودار وسط) و الگوريتم متمرکز (نمودار پايين).
ردگیری توزیعشده مانند روشی که در این مقاله با آن مقایسه صورت گرفته است (یعنی روش مبتني بر گراف [12]) دارد. به عنوان پیشنهادی برای آينده ميتوان از الگوريتمهایی استفاده کرد که کاهش دقت ردگیری را تا حدود بيشتري جبرانسازي نمایند.
مراجع
[1] Z. Ying and L. Gao, "Sensor-networked underwater target tracking based on grubbs criterion and improved particle filter algorithm," IEEE Access, vol. 7pp. 142894-142906, 2019.
[2] Z. Hao, Z. Xue, W. Zhuping, Y. Huaicheng, and S. Jian, "Adaptive consensus-based distributed target tracking, with dynamic cluster in sensor networks," IEEE Trans. on Cybernetics, vol. 5, no. 5, pp. 1580-1591, May 2018.
[3] R. Jesse, K. Achutegui, and J. Miguez, "A distributed particle filter for nonlinear tracking in wireless sensor networks," Signal Processing, vol. 98, pp. 121-134, May 2014.
[4] F. Zhao and L. Guibas, Wireless Sensor Networks: An Information Processing Approach, Morgan Kaufmann, San Francisco, CA, USA, 2004.
[5] W. Zhao and Y. Liang, "Energy-efficient and robust in-network inference in wireless sensor networks," IEEE Trans. on Cybernetics, vol. 45, no. 10, pp. 2105-2118, Oct. 2015.
[6] O. Hlinka, F. Hlawatsch, and P. Djuric, "Distributed particle filtering in agent networks: a survey, classification, and comparison," IEEE Signal Processing Magazine, vol. 30, no. 1, pp. 61-81, Jan. 2012.
[7] L. Xiao and S. Boyd, "Fast linear iterations for distributed averaging," Syst. Contr. Lett., vol. 53, no. 1, pp. 65-78, Sept. 2004.
[8] S. Farahmand, S. I. Roumeliotis, and G. B. Giannakis, "Set-membership constrained particle filter: distributed adaptation for sensor networks," IEEE Trans. Signal Processing, vol. 59, no. 9, pp. 4122-4138, Sept. 2011.
[9] D. Gu, J. Sun, Z. Hu, and H. Li, "Consensus based distributed particle filter in sensor networks," in Proc. Int. Conf. Inform. Automationpp. 302-307, Changsha, China, 20-23 Aug. 2008.
[10] Y. Xu, K. Xu, J. Wan, Z. Xiong, and Y. Li, "Maneuvering target tracking by using particle filter," in Proc. IEEE Joint 9th IFSA World Congress and 20th NAFIPS Int. Conf., pp. 2223-2228, Vancouver, Canada, 25-28 Jul. 2002.
[11] O. Hlinka, O. Sluciak, F. Hlawatsch, P. Djuric, and M. Rupp, "Likelihood consensus and its application to distributed particle filtering," IEEE Trans. on Signal Processing, vol. 60, no. 8, pp. 4334-4349, Aug. 2012.
[12] J. Y. Yu, M. J. Coates, and M. G. Rabbat, "Graph-based compression for distributed particle filters," IEEE Trans. on Signal and Information Processing over Networks, vol. 5, no. 3, pp. 404-417, Sept. 2019.
[13] A. Mohammadi and A. Asif, "Distributed consensus + innovation particle filtering for bearing/range, tracking with communication constraints," IEEE Trans. on Signal Processing, vol. 63, no. 3, pp. 620-635, Feb. 2014.
ایمان مقصودلو در سال 1386 مدرك كارشناسي مهندسي برق خود را از دانشگاه صنعتی خواجه نصیر الدین طوسی و در سال 1393 مدرك كارشناسي ارشد مهندسي برق در گرایش رادیو الکترونیک را از دانشگاه صنعتی مالک اشتر دریافت نموده است و اکنون دانشجوی دکتری مهندسی مخابرات در دانشگاه جامع امام حسین (ع) می باشد. وی از سال 1393 تا کنون در موسسه تحقیقات مخابرات نظری مشغول فعالیت می باشد. زمینههای علاقهمندی وی عبارتند از: سیستم های مخابراتی، پردازش سیگنال آماری، و مخابرات چند ورودی چند خروجی.
میثم رئیس دانائی در سال 1383 مدرك كارشناسي مهندسي برق خود را از دانشگاه صنعتي امیر کبیر و در سال های 1385 و 1391 بترتیب مدرك كارشناسي ارشد مهندسي برق و مدرک دکترای مهندسی برق گرایش مخابرات سیستم خود را هر دو از دانشگاه صنعتی شریف دريافت نمود. دكتر رئیس دانائی از سال 1392 در دانشكده مهندسي برق دانشگاه جامع امام حسین (ع) در تهران مشغول به فعاليت گرديد و اينك نيز عضو هيأت علمي اين دانشكده ميباشد. زمينههاي علمي مورد علاقه نامبرده متنوع بوده و شامل موضوعاتي مانند پردازش سیگنال آماری، تئوری تخمین، مکانیابی سیستمهای مخابراتی و نسل پنجم شبکه های مخابراتی ميباشد.
حمید آرزومند در سال 1387 مدرك كارشناسي مهندسي برق خود را از دانشگاه امام حسین (ع) و در سال 1391 مدرك كارشناسي ارشد مهندسي برق خود را از دانشگاه تربیت مدرس و در سال 1399 مدرک دکترای مهندسی برق گرایش مخابرات سیستم خود را از دانشگاه فردوسی مشهد دريافت نمود. دكتر آرزومند از سال 1386 تا کنون در دانشكده مهندسي برق دانشگاه جامع امام حسین (ع) در تهران بهعنوان پژوهشگر مشغول به فعاليت است. زمينههاي علمي مورد علاقه نامبرده متنوع بوده و شامل موضوعاتي مانند تئوری تخمین و آشکارسازی، پردازش سیگنال آماری و مکانیابی ميباشد.
[1] . Connected Graph
[2] . Root Mean Square Position Error