الگوریتم اولیه- دوگانه توزیع شده با پارامترهای متغیر و ساختار مشارکتی افزایشی دوجهته
محورهای موضوعی : مهندسی برق و کامپیوتر
قنبر آذرنیا
1
(دانشگاه صنعتی ارومیه)
کلید واژه: الگوریتم پارامتر متغیر, بازسازی توزیع‌شده, حسگری فشرده, مد افزایشی دوجهته,
چکیده مقاله :
به دلیل شرایط خاص شبکه‌های حسگری بی‌سیم از نقطه‌نظرهایی نظیر محدودیت انرژی، تسریع سرعت همگرایی الگوریتم‌های این حوزه اهمیت پیدا می‌کند. این امر در مورد حسگری فشرده توزیع‌شده که فاز بازسازی پیچیده‌ای دارد، ضروری‌تر به نظر می‌رسد. بر همین اساس در این مقاله، الگوریتم بازسازی حسگری فشرده توزیع‌شده‌ای ارائه می‌شود که امکان بازسازی با نرخ همگرایی بهبودیافته‌تری را میسر می‌سازد. الگوریتم پیشنهادی، یک الگوریتم اولیه- دوگانه توزیع‌شده در یک ساختار افزایشی دوجهته است که در آن پارامترها با زمان تغییر می‌کنند. تغییرات پارامترها به‌صورت ضابطه‌مند و برای آن دسته از مسائل بهینه‌سازی محدبی انجام می‌گیرد که در آنها توابعی که بیان‌کننده قید مسئله و مدل‌کننده مشارکت بین گره‌ها هستند، قویاً محدب می‌باشند. شیوه پیشنهادی با شبیه‌سازی‌هایی تضمین شده که نشان از عملکرد بالای الگوریتم پیشنهادی به لحاظ سرعت همگرایی، حتی در شرایط سختگیرانه‌تری نظیر تعداد اندک اندازه‌گیری‌ها و یا درجه تنکی پایین‌تر دارد.
Special conditions of wireless sensor networks, such as energy limitation, make it essential to accelerate the convergence of algorithms in this field, especially in the distributed compressive sensing (DCS) scenarios, which have a complex reconstruction phase. This paper presents a DCS reconstruction algorithm that provides a higher convergence rate. The proposed algorithm is a distributed primal-dual algorithm in a bidirectional incremental cooperation mode where the parameters change with time. The parameters are changed systematically in the convex optimization problems in which the constraint and cooperation functions are strongly convex. The proposed method is supported by simulations, which show the higher performance of the proposed algorithm in terms of convergence rate, even in stricter conditions such as the small number of measurements or the lower degree of sparsity.
[1] ح. نظری، م. رئیس‌دانایی و م. سپه‌وند، "مکان‌یابی بر اساس تفاضل توان سیگنال دریافتی با به‌کارگیری بهینه‌سازی محدب در شبکه حسگر بی‌سیم،" نشريه مهندسی برق و مهندسی کامپيوتر ايران، ب- مهندسي كامپيوتر، سال 17، شماره 4، صص. 310-306، زمستان 1398.
[2] ف. پدیداران مقدم و ح. مقصودی، "مسیریابی بهبودیافته برای توازن بار در شبکه حسگر بی‌سیم در بستر اینترنت اشیا بر پایه الگوریتم کلونی مورچگان چندگانه،" فصلنامه فناوری اطلاعات و ارتباطات ایران، سال 14، شماره 52/51، صص. 255-220، تابستان 1401.
[3] ق. آذرنیا، م. ع. طینتی و ت. یوسفی رضایی، "الگوریتم توزیع‌شده و مشارکتی به‌منظور بازسازی سیگنال‌های تنک در شبکه‌های حسگری بی‌سیم با توپولوژی افزایشی دوجهته،" فصلنامه علمی پردازش علائم و داده‌ها، جلد 18، شماره 3، صص. 76-65، زمستان 1400.
[4] ق. آذرنیا و ع. ع. شریفی، "الگوریتم طول متغیر کسری نفوذی با قابلیت پیشبرد مشارکت مبتنی بر گرادیان برای افزایش کارایی شبکه‌های تطبیقی با لینک‌های نویزی،" مجله علمی پژوهشی رایانش نرم و فناوری اطلاعات، جلد 10، شماره 4، صص. 14-1، زمستان 1400.
[5] S. El Khediri, "Wireless sensor networks: a survey, categorization, main issues, and future orientations for clustering protocols," Computing, vol. 104, no. 8, pp. 1775-1837, Aug. 2022.
[6] G. Azarnia and A. A. Sharifi, "Steady-state analysis of distributed incremental variable fractional tap-length LMS adaptive networks," Wireless Networks, vol. 27, no. 7, pp. 4603-4614, 2021.
[7] G. Azarnia, "Diffusion fractional tap-length algorithm with adaptive error width and step-size," Circuits, Systems, and Signal Processing, vol. 41, no. 1, pp. 321-345, Jan. 2022.
[8] G. Azarnia, M. A. Tinati, A. A. Sharifi, and H. Shiri, "Incremental and diffusion compressive sensing strategies over distributed networks," Digital Signal Processing, vol. 101, Article ID: 102732, Jun. 2020.
[9] C. Li, G. Li, and P. K. Varshney, "Distributed detection of sparse signals with censoring sensors in clustered sensor networks," Information Fusion, vol. 83/84, pp. 1-18, Jul. 2022.
[10] G. Azarnia and A. A. Sharifi, "Fully cooperative and distributed focal underdetermined system solver compressive sensing recovery algorithm for wireless sensor networks," International J. of Communication Systems, vol. 35, no. 9, Article ID: e5126, Jun. 2022.
[11] O. Karpis, et al., "Compressed sensing-a way to spare energy in WSN for UAV," IFAC-PapersOnLine, vol. 55, no. 4, pp. 170-176, 2022.
[12] A. Salim, W. Osamy, A. M. Khedr, A. Aziz, and M. Abdel-Mageed, "A secure data gathering scheme based on properties of primes and compressive sensing for IoT-based WSNs," IEEE Sensors J., vol. 21, no. 4, pp. 5553-5571, 15 Feb. 2020.
[13] Y. Xu, G. Sun, T. Geng, and B. Zheng, "Compressive sparse data gathering with low-rank and total variation in wireless sensor networks," IEEE Access, vol. 7, pp. 155242-155250, 2019.
[14] C. Wang, X. Shen, H. Wang, and H. Mei, "Energy-efficient collection scheme based on compressive sensing in underwater wireless sensor networks for environment monitoring over fading channels," Digital Signal Processing, vol. 127, Article ID: 103530, Jul. 2022.
[15] M. Al Mazaideh and J. Levendovszky, "A multi-hop routing algorithm for WSNs based on compressive sensing and multiple objective genetic algorithm," J. of Communications and Networks, vol. 23, no. 2, pp. 138-147, Apr. 2021.
[16] J. Chen, et al., "Factor graphs for support identification in compressive sensing aided wireless sensor networks," IEEE Sensors J., vol. 21, no. 23, pp. 27195-27207, 1 Dec. 2021.
[17] R. Torkamani, H. Zayyani, and R. A. Sadeghzadeh, "Model-based decentralized Bayesian algorithm for distributed compressed sensing," Signal Processing: Image Communication, vol. 95, Article ID: 116212, Jul. 2021.
[18] F. Amini, Y. Hedayati, and H. Zanddizari, "Exploiting the inter-correlation of structural vibration signals for data loss recovery: a distributed compressive sensing-based approach," Mechanical Systems and Signal Processing, vol. 152, Article ID: 107473, May 2021.
[19] G. Azarnia, "Distribution agnostic Bayesian compressive sensing with incremental support estimation," Multidimensional Systems and Signal Processing, vol. 33, no. 2, pp. 327-340, Jun. 2022.
[20] A. Chambolle and T. Pock, "A first-order primal-dual algorithm for convex problems with applications to imaging," J. of Mathematical Imaging and Vision, vol. 40, no. 1, pp. 120-145, May 2011.
نشریه مهندسی برق و مهندسی کامپیوتر ایران، ب- مهندسی کامپیوتر، سال 21، شماره 2، تابستان 1402 129
مقاله پژوهشی
الگوریتم اولیه- دوگانه توزیع‌شده با پارامترهای متغیر
و ساختار مشارکتی افزایشی دوجهته
قنبر آذرنیا
چکیده: به دلیل شرایط خاص شبکه‌های حسگری بی‌سیم از نقطه‌نظرهایی نظیر محدودیت انرژی، تسریع سرعت همگرایی الگوریتم‌های این حوزه اهمیت پیدا می‌کند. این امر در مورد حسگری فشرده توزیع‌شده که فاز بازسازی پیچیده‌ای دارد، ضروری‌تر به نظر می‌رسد. بر همین اساس در این مقاله، الگوریتم بازسازی حسگری فشرده توزیع‌شده‌ای ارائه می‌شود که امکان بازسازی با نرخ همگرایی بهبودیافته‌تری را میسر می‌سازد. الگوریتم پیشنهادی، یک الگوریتم اولیه- دوگانه توزیع‌شده در یک ساختار افزایشی دوجهته است که در آن پارامترها با زمان تغییر می‌کنند. تغییرات پارامترها به‌صورت ضابطه‌مند و برای آن دسته از مسائل بهینه‌سازی محدبی انجام می‌گیرد که در آنها توابعی که بیان‌کننده قید مسئله و مدل‌کننده مشارکت بین گره‌ها هستند، قویاً محدب می‌باشند. شیوه پیشنهادی با شبیه‌سازی‌هایی تضمین شده که نشان از عملکرد بالای الگوریتم پیشنهادی به لحاظ سرعت همگرایی، حتی در شرایط سختگیرانه‌تری نظیر تعداد اندک اندازه‌گیری‌ها و یا درجه تنکی پایین‌تر دارد.
کلیدواژه: الگوریتم پارامتر متغیر، بازسازی توزیع‌شده، حسگری فشرده، مد افزایشی دوجهته.
1- مقدمه
محدودیت‌های توان و پهنای باند در شبکه‌های حسگری بی‌سیم، طراحی‌ها، پیکربندی‌ها و الگوریتم‌های مرتبط با چنین شبکه‌هایی را به چالش کشیده است [1] تا [5]. برای رفع این چالش، پردازش‌های توزیع‌شده و مشارکتی [6] و [7] در قالب توپولوژی‌های مختلف [8] در شبکه‌های حسگری بی‌سیم مورد توجه قرار گرفته است.
در برخی از کاربردهای شبکه‌های حسگری بی‌سیم، سیگنال‌ها اغلب نوعی ساختار را شامل می‌شوند که پردازش و نمایش هوشمند را برای آنها ممکن می‌سازد. ساختاری که اخیراً در این قبیل شبکه‌ها مورد توجه قرار گرفته است، تنکی2 سیگنال مورد پردازش می‌باشد [9]. سیگنال تنک، سیگنالی است که اکثر درایه‌های آن صفر باشد. در یک بیان دیگر، یک سیگنال 
تنک نامیده می‌شود، اگر حداکثر 
درایه غیرصفر را شامل شود. این ویژگی از سیگنال به استفاده توزیع‌شده از تکنیک حسگری فشرده3 در شبکه‌های حسگری بی‌سیم انجامیده است [10] و [11]. از جمله کاربردهای حسگری فشرده در شبکه‌های حسگری بی‌سیم می‌توان به کاربرد آن در جمع‌آوری داده و مسیریابی اشاره کرد [12] تا [15].
در [16] حسگری فشرده در شبکه‌های حسگری بی‌سیم از نقطه‌نظر تشخیص ساپورت (مکان ورودی‌های غیرصفر در یک سیگنال تنک) مورد توجه قرار گرفته است.
در [17] یک الگوریتم حسگری فشرده توزیع‌شده بیزین مبتنی بر مدل پیشنهاد شده که از هر دو همبستگی درون سیگنالی و بین سیگنالی برای بازیابی توأم چندین سیگنال تنک استفاده می‌کند.
در [18] بازیابی داده‌های ازدست‌رفته چندین سیگنال با نسبت تلفات متغیر بررسی شده و برای این منظور، [18] همبستگی بین سیگنالی را مورد توجه قرار داده و از حسگری فشرده توزیع‌شده بهره گرفته است.
در [19] یک روش بیزین برای بازیابی توزیع‌شده سیگنال‌های تنک ارائه گردیده که نسبت به توزیع ساپورت، وفقی بوده و نیازی به معلوم‌بودن توزیع ساپورت ندارد. در شیوه پیشنهادی [19] در شبکه‌ای از حسگرها، بازسازی یک سیگنال تنک به‌طور مشارکتی و بر اساس مد همکاری افزایشی انجام می‌گیرد. در این روش، هر گره معیار تشخیص ساپورت غالب را از گره قبلی خود دریافت، مقدار معیار تشخیص ساپورت غالب خود را به آن اضافه و نتیجه را به گره بعدی ارسال می‌کند. در آخرین گره حلقه، داده‌های کل شبکه برای تصمیم‌گیری در مورد ساپورت غالب مورد استفاده قرار می‌گیرد که این بهره‌گیری از دایورسیتی مکانی در فرایند تشخیص ساپورت عملکرد برتری نتیجه می‌دهد.
در [3] یک الگوریتم بازسازی حسگری فشرده توزیع‌شده با مشارکت همه گره‌های شبکه ارائه گردیده که در آن، عملکرد حالت دائم بهتر و پیچیدگی پایین محاسباتی، مهم‌ترین مشخصه این الگوریتم به شمار می‌رود. الگوریتم پیشنهادی [3] یک الگوریتم بازگشتی اولیه- دوگانه است که با بهینه‌سازی ضرایب لاگرانژ حاصل شده است. این الگوریتم در چهارچوب مد مشارکتی افزایشی دوجهته ارائه گردیده که در آن هر حسگر در هر تکرار تنها با دو گره همسایه خود به تبادل داده می‌پردازد. لذا در مقایسه با ساختار مشارکتی نفوذی [10] که در آن هر حسگر با تمام گره‌های همسایه خود به تبادل داده می‌پردازد، شیوه پیشنهادی [3] به میزان قابل ملاحظه‌ای مصرف توان پایین‌تری دارد. شیوه پیشنهادی [3] یک چهارچوب توزیع‌شده جامع برای بازسازی سیگنال‌های تنک در شبکه‌های حسگری بی‌سیم است که می‌توان آن را در قالب مسائل بهینه‌سازی محدب متفاوتی پیاده کرد. مزیت مسائل محدب نسبت به مسائل غیرمحدب این است که در مسائل بهینه‌سازی محدب، یک بهینه مطلق را می‌توان در اکثر موارد با دقت خوب در مدت زمانی معقول و مستقل از مقداردهی اولیه محاسبه کرد.
نقطه ضعف الگوریتم ارائه‌شده در [3] وجود پارامترهایی است که نحوه انتخاب آنها تأثیر مستقیمی بر همگرایی و سرعت همگرایی این الگوریتم دارد. در اینجا قصد داریم تا نحوه انتخاب این پارامترها را در راستای تسریع‌بخشیدن به سرعت همگرایی این الگوریتم فرمول‌بندی کنیم. در این مقاله، تحلیلی ریاضی پیرامون شیوه ارائه‌شده در [3] را ارائه خواهیم داد. در نتیجه تحلیل انجام‌گرفته، اولاً شرایط لازم برای همگرایی این الگوریتم استخراج خواهد شد و ثانیاً روابطی بازگشتی برای پارامترهای اساسی این الگوریتم ارائه خواهیم داد که انتخاب پارامترها بر اساس این روابط، همگرایی الگوریتم را تسریع خواهد نمود. شیوه پارامتر متغیر پیشنهادی می‌تواند در قالب تمام آن دسته از مسائل بهینه‌سازی پیاده شود که در آنها توابعی که بیان‌کننده قید مسئله و مدل‌کننده مشارکت بین گره‌ها هستند، قویاً محدب4 باشند.
مطالعات ما نشان دادند که در [20]، الگوریتمی برای تسریع همگرایی مسائل بهینه‌سازی محدب اولیه- دوگانه و برای مسائلی که درجه‌ای از همواری را شامل می‌شوند، ارائه گردیده است. اما شیوه [20] با روش پیشنهادی ما در این مقاله تفاوت‌های اساسی دارد. نخست اینکه الگوریتم پیشنهادی [20] شیوه توزیع‌شده‌ای نبوده و برای بازسازی یک سیگنال به‌صورت غیرمشارکتی در یک گره منفرد می‌تواند کاربرد داشته باشد؛ حال آنکه شیوه پیشنهادی ما در قالب شبکه‌های حسگری بیان شده است. همین امر، تحلیل‌های صورت‌گرفته در این مقاله را پرچالش‌تر کرده و باید در تحلیل‌های ریاضی انجام‌گرفته، اثر مشارکت بین گره‌ها را نیز منظور کنیم. همچنین در نتیجه مشارکت بین گره‌ها پارامتر دیگری وارد الگوریتم پیشنهادی [3] شده که استخراج قیدهایی برای این پارامتر به‌منظور تضمین همگرایی الگوریتم و یافتن رابطه‌ای برای این پارامتر در کنار دیگر پارامترها برای تسریع همگرایی الگوریتم، خود چالش دیگری است.
2- مسئله حسگری فشرده
2-1 بیان مسئله
از جمله مسائل عملی پرکاربرد در پردازش سیگنال، مسئله بازسازی سیگنال 
از داده مشاهده‌شده 
است که در آن ماتریس حسگری 
فرایند اندازه‌گیری خطی را مدل می‌کند. مادامی که 
باشد، این مسئله یک مسئله مرسوم در جبر کلاسیک خطی بوده و با روش‌های کلاسیک قابل حل است. اما زمانی که تعداد مشاهدات 
کمتر از طول 
سیگنال 
باشد، بدون اطلاعات اضافی‌تر، بازسازی از مشاهدات ممکن نخواهد بود. یکی از فرضیاتی که بازسازی سیگنال مطلوب را در چنین شرایطی ممکن می‌سازد، تنکی این سیگنال است به این معنا که اکثر درایه‌های صفر باشد. تحت فرض تنکی، الگوریتم 
تنک‌ترین برداری را نتیجه خواهد داد که با داده مشاهده‌شده 
سازگار باشد. اما از آنجایی که این الگوریتم در حالت کلی یک مسئله NP-hard است، الگوریتم‌های کارایی با قابلیت پیاده‌سازی در حسگری فشرده ارائه گردیده‌اند. این الگوریتم‌ها را می‌توان در چند دسته جای داد: شیوه‌های بهینه‌سازی محدب [10]، روش‌های حریصانه، روش‌های مبتنی بر آستانه [8]، شیوه‌های بهینه‌سازی غیرمحدب، الگوریتم‌های ترکیبی یا زیرخطی و روش‌های آماری [17].
وقتی مسئله حسگری فشرده در چهارچوب شبکه‌های سنسوری بی‌سیم مطرح می‌شود، الگوریتم‌های بازسازی سازگاریافته برای این چهارچوب، علاوه بر اینکه باید به‌طور منطقی سریع باشند، باید قابلیت پیاده‌سازی مشارکتی و توزیعی را دارا باشند؛ موردی که بر چالش طرح الگوریتم‌های بازسازی در این چهارچوب می‌افزاید. یکی از چنین الگوریتم‌های کارایی در [3] ارائه شده که در ادامه به معرفی این الگوریتم خواهیم پرداخت.
2-2 الگوریتم اولیه- دوگانه توزیعی با توپولوژی افزایشی دوجهته
یک شبکه حسگری بی‌سیم شامل 
حسگر را در نظر می‌گیریم. مأموریت این شبکه آن است که هر حسگر با داشتن بردار اندازه‌گیری 
و ماتریس اندازه‌گیری 
سیگنال تنک را به نحوی بازسازی کند که 
با 
برقرار باشد. برای این منظور، [3] مسئله بهینه‌سازی زیر را در نظر گرفته است
(1)
که 
و 
توابع محدب، نیمه‌پیوسته پایین‌تر5