Báo cáo tóm tắt đề tài - Xây dựng thuật toán tối ưu đánh giá tính bền vững (robustness) của hệ thống điều khiển được kết nối mạng (networked control system - Necs)

crA riNn nEx vuNc (RoBUSTninss; cua n4, rn$nC o$u xnrEN Dttgc rfr NOI M4'NG (NETWORKED CONTROL SYSTEM-NECS) Mi s6: 82016-DN02-03 Xic nhin cfra t6 chrfrc chfr tri Chfr nhipm aA tai (ry, hp ftn) ,a /l'tttp-'' ---,rlta POS. TS. LE MI KM OANH TrAn ThiMinh Dung DN NN Th6ne 0312019 DANH SACn XSUNC rnAXs Vrf,X THAM GIA NGHITX CtU Ot r^q.I 1. fran fni Minh Dung 2. Luu Nggc An 3. Gi6p Quang HuY Eor\I vI PH6r nqp cHiNH 1. NECS team, GIPSA-LAB, Grenoble, France. 2. Nguli d4i diQn: Alain Y, Kibangou 3. N,6i dung ph$i hgrp: Nghi6n cr?u vd "Consensus", vi nhimg ung dUng cria n6 trong tliOu khi€n cfrng nhu trong tinh vlrc giao thdng EAr Hec oa NANc DAI Hec nAcn KHoA oL NANc ru0xc rrw xnr euA ncrutx cuTr 1. Thdng tin chung: - TCn dA tdi: Xdy dpng thuflt to6n tdi uu d6nh gi6 tinh b€n virng cria hQ th6ng diOu khi€n dugc ktit nol mang - Md s6: 82016- EN02-03 - Chn nhiQm OO tai: TS. TrAn ThiMinh Dung - Td chric chri tri: Trulng D4i Hgc B6ch Khoa DdNfng - Thdi gian thuc hiQn: Th6ng 1012016 d5n th6ng 3/2019 (gia h3n 6 th6ng) 2. Mgc ti6u: Ktit hgp phucrng ph6p t6i uu h6a vd thuft to6n d6ng thugn dC de xu6t ra phuong phrip tl6nh gi6 dQ bAn vnngina *ang tiOi ! 3. Tinh moi vi s6ng tgo: Thuflt ngt vA consensus trong di€u k:hiOn xem nhu rdt mdi me d6i vdi cQng dOng nghiOn cr?u d ViQt Nam, trong khi d tr0n,th6 gi6i tte tdn t4i duo. c hon thflp ni6n. Chring ta chi bitit vA tlctr sri ph6t tri6n consensus t6n t4i trong khoa hgc m6y tinir, cfing nhu trong khoa "hi hgc xd hQi vi.kinh tti. ffrti nhrmg, viQc img dung khdi nigrn consensus vdo trong ki thudt, IiCu.thien md ra.mQt th6 gi6i hodn todn mdi. ViQc k6t hqp-gitia tbuAt to6n d6ng thufln va phuong pitap tOi uu h6a dd d6nh gi6 ttO bAn virng cria meng ludi cting li tli6m s6ng t4o ul la tuan Aiem noan toin m6i trong nghiOn cr?u tpi ViQt Nam cfrng nhu tr6n thi5 gi6i. 4.Xfitqui nghi6n cf,u: . Xay dlmg dugc phuong ph6p d6nh gi6 dQ bOn virng cria mpng lu6i . Virit chuong trinh m6 ph6ng ktit qud d6nh gi6 phuong ph6p riO xudt 5. Sin phim: o 02 bdi b6o ddng tr€n tpp chf trong nudc: * "NghiOn ciru v€ thuat to6n d6ng thufn cho hp th6ng da rIOi tugng". Tap chi KHCN DHEN. SO OltO:;, trang3'-3i,20t6 t" "Optimization_m_ethod in designing a finiteltime average consensus protocol,,. Tpp chf KHCN EHDN. 56 12(133), trang l-5,201g 01 bei b6o SCIe: "Collaborative Network Monitoring by means of Laplacian Spectrum Estimation and Average Consensus", Intemational Journal of Control, Automaiion and System, 2019, Accepted 02 hqc vi0n cao hoc bio v0 thenh c6ng: * Nguy6n Vdn Nghia, "Ilng dung thuflt to6n ddng thu{n diAu kti6n btr m6t Ai5i xung trong lu6i dipn siOu nh6 dQc lfp",t6o vQ thinh cdng th6ng 612018, {. Phan Anh Tudn, "E6nh gi6 tinh bdn virng cria hQ th5ng da <ttii tugng bing phuong ph6p tdi uu h6a", bio vQ thenh c6ng th6ng l2l20l8 . 01 s6ch tham khio: "Methods for finite-time average consensus protocols design - methods and applications", Lambert Academic Publishing, 1112016,978-3-659-96090-l r 0l phuongph6p dAxu6t o 01 chucrng trinh m6 ph6ng 6. Phuong thlic chuy6n giao, ttla chi rfrng dgngo tfc tlQng vn lgi ich mang l4i cfra k6t qui nghiOn cfu: C6 thd sri dgng ldm tdi liQu nghi0n criru cho gi6ng vi6n vi hgc viOn cao hgc. NSdy 28 thdng 02 ndm 2019 T6 chfc chfr tri Chfr nhiQm ad tai (lry, hp vd t€n) , h** "5- ---Ty'tt '' Tr,in Thi Minh Dung INFORMATION ON RESEARCH RESULTS 1. General information: Project title: Designing a method for robustness assessment of a networked control system. Code number: B2016-DDN02-03 Coordinator: PhD. Tran Thi Minh Dung Implementing institution: University of Danang - University of Science and Technology Duration: from 10/2016 to 10/2018 extended to 3/2019 2. Objective(s): Proposing a method to assess the robustness of a networked control system by combining the consensus algorithm with the optimization method 3. Creativeness and innovativeness: The terminology “consensus” has appeared for a long time in the literature. However, the consensus applied in control seems to be new for the research community in Vietnam. We are familiar with the development history of consensus in economic, computer science and also in society science. But, the application of consensus in technology and control obviously opens the gate to the world. The integration between consensus algorithm and the optimization method to assess the robustness of the network is the creativeness and the innovativeness in recent research tendency. 4. Research results:  Proposed a method for network robustness assessment  A Matlab code to validate the proposed method 5. Products:  01 article published in domestic journal  01 SCIE article pulished in national journal  02 Master candidates  01 method  01 programming code 6. Transfer alternatives, application institutions, impacts and benefits of research results: This project can be used as a reference for lecturers, researchers and master candidates i Mục lục 1 Mở đầu 1 1.1 Hệ thống mạng lưới điều khiển.............................1 1.2 Tính cấp thiết của đề tài.................................1 1.3 Mục tiêu đề tài.....................................2 1.4 Đối tượng nghiên cứu..................................2 1.5 Phạm vi nghiên cứu...................................2 1.6 Cách tiếp cận và phương pháp nghiên cứu.......................2 1.6.1 Cách tiếp cận..................................2 1.6.2 Phương pháp nghiên cứu............................2 2 Tổng quan về thuật toán “Consensus”5 2.1 Lý thuyết đồ thị.....................................5 2.2 Thuật toán đồng thuận.................................5 2.2.1 Phân loại thuật toán đồng thuận........................6 2.2.2 Định nghĩa...................................6 3 Phương pháp mới để đánh giá tính bền vững của NeCS7 3.1 Độ bền vững của mạng lưới...............................7 3.1.1 Độ phản kháng của đồ thị...........................7 3.2 Đánh giá tính bền vững của mạng lưới theo hình thức phân tán............7 4 Phương pháp tối ưu hoá đánh giá tính bền vững9 4.1 Tính toán các giá trị riêng của ma trận Laplacian riêng biệt..............9 4.2 Tính toán các giá trị riêng từ ma trận đồng thuận trung bình.............. 12 5 Mô phỏng bằng Matlab 13 5.1 Sơ đồ kết nối gốc.................................... 14 6 Kết luận 17 Bibliography 19 iii Danh sách hình vẽ 2.1 Đồ thị G(V,E) ......................................5 2.2 (a) điều kiện ban đầu, (b) trạng thái xác lập......................6 5.1 Một lưới điện nhỏ với 6 DG............................... 13 5.2 Quỹ đạo của các nút................................... 14 5.3 Bình phương sai số trung bình giữa giá trị tính được và giá trị thực của ci (MSEc) và x¯i (MSEx)......................................... 15 v Danh sách bảng 5.1 Thông số của các DGs................................. 13 5.2 Các thông số đạt được từ thuật toán đề xuất với sự biến thiên của γ .......... 15 vii List of Abbreviations MAS Multi-agent System FC Fusion Center WSN Wireless Sensor Network ADMM Alternating Direction of Multipliers Method MSE Mean Square Error FFT Fast Fourier Transform NECs Networked Control Systems DG Distributed Generation 1 Chương 1 Mở đầu 1.1 Hệ thống mạng lưới điều khiển Hệ thống mạng lưới điều khiển (Networked control system-NeCS) cũng là một hệ thống đa biến MAS. Hiện nay, một ví dụ rất được quan tâm là mạng lưới cảm biến không dây (Wireless Sensor Network). Hệ thống này được tìm thấy trong rất nhiều lĩnh vực như những ứng dụng trong quân sự (giám sát chiến trường), các ứng dụng trong môi trường (phát hiện cháy rừng, phát hiện thức ăn), những ứng dụng trong vấn đề sức khoẻ (nghiên cứu dữ liệu sinh lý của cơ thể người), tự động hoá toà nhà, điều khiển tập quán. . . Một hệ thống điều khiển là một thiết bị hoặc một tổ các thiết bị dung để quản lý, chỉ huy, định hướng hoặc điều chỉnh hành vi của các thiết bị hoặc hệ thống khác. Sự ra đời của mạng lưới truyền thông, giới thiệu các khái niệm về kiểm soát từ xa một hệ thống, trong đó đã cho ra đời hệ thống điều khiển mạng lưới (networked control systems-NECs). Những năm qua, mạng cảm biến, bao gồm các thiết bị tự động và giao tiếp, có thể đặc biệt quan tâm đúng mức đến tiềm năng to lớn của họ về các ứng dụng và các vấn đề khoa học và công nghệ mới mà họ đưa ra. Ví dụ, chúng được sử dụng để ước lượng các thông số cả tĩnh và động (trường hợp mật độ xe, phân loại xe, phát hiện những thay đổi về công suất trong hệ thống giao thông thông minh). Giả sử rằng các cảm biến các nút được trang bị đầy đủ tài nguyên máy tính và truyền thông, các vấn đề của dự toán phân phối bao gồm trong việc ước tính các thông số, không phải bằng cách kết hợp các phép đo (có thể là nhiễu) tại một nút trung tâm nhưng bằng cách phân phối các tính toán trên tất cả các nút trong mạng. Lợi ích của phương pháp này là để giảm sự tổn thương của mạng và khối lượng dữ liệu truyền tải và phân phối tải trọng tính toán trên mạng. Hiện nay, giải pháp thường được thông qua sự đồng thuận (consensus) giữa các cảm biến các nút khác nhau trong mạng. Như vậy, dựa vào những thông tin cục bộ và sự tương tác qua lại giữa các đối tượng, làm thể nào để các đối tượng cùng đạt đến sự đồng thuận? Vấn đề này được gọi là vấn đề đồng thuận (consensus problem) nó được thiết kế cho một giao thức mạng lưới dựa trên thông tin cục bộ thu được bởi mỗi đối tượng sao cho tất cả đối tượng cuối cùng sẽ đạt đến sự đồng ý trên một số đại lượng nhất định. 1.2 Tính cấp thiết của đề tài Các vấn đề đồng thuận (consensus) có thể được phân tích theo hình thức của hệ thống thời gian liên tục hoặc của những người thời gian rời rạc. Vấn đề đồng thuận đã nhận được sự quan tâm rất lớn từ cộng đồng nghiên cứu khác nhau do các ứng dụng rộng rãi trong nhiều lĩnh vực bao gồm cảm biến đa dữ liệu hợp nhất (multi-sensor data fusion), đổ hành vi của bầy đàn (flocking behavior of swarm), multi-vehicle formation control, phân tán tính toán (distributed computation), vấn đề “rendez-vous”. . . Cụ thể hơn, các thuật toán thống nhất trung bình (nghĩa là thỏa thuận tương ứng với mức trung bình của các giá trị ban đầu) thường được sử dụng như một khối cho một số kiểm soát, lập dự toán hoặc suy luận thuật toán phân tán. Tính hiệu quả của một mạng lưới được đánh giá thông qua các chức năng và tính bền vững của nó. Nhắc đến điều này, một vài câu hỏi sẽ được đặt ra: nếu có một sự kiện ngẫu nhiên nào đó xảy ra, 2 Chương 1. Mở đầu Mạng sẽ phản ứng như thế nào? Có thể tồn tại tiếp tục hay không? Hơn thế nữa, sự hiểu biết về tính bền vững của Mạng có thể bảo vệ và cải thiện hiệu suất của Mạng một cách hiệu quả. Nó cũng được sử dụng để thiết kế những Mạng mới có thể hoạt động tốt khi đối mặt với những lỗi hoặc khi bị tấn công. Để trả lời cho những câu hỏi này thì những nghiên cứu về tính bền vững của Mạng thu hút rất mạnh mẽ đối với những nhà nghiên cứu. Nghiên cứu mới trong điều khiển rất được chú ý gần đây: tính đồng thuận “Consensus” trong hệ thống điều khiển mạng lưới (Networked control system-NeCS). Thuật toán “Consensus” được ứng dụng trong rất nhiều lĩnh vực kĩ thuật. Đặc biệt, trong lĩnh vực điều khiển (điều khiển hợp tác (cooperative control), tối ưu hoá và ứơc lượng, điều khiển phân tán. . . ). Nghiên cứu về “consensus”, ta có thể bước vào nghiên cứu đối với hệ thống phân tán độc lập (distributed control system) và hệ đa đối tượng (multi-agent system). . . Chính vì vậy, đề tài nghiên cứu này sẽ ứng dụng “Consensus” trong việc đánh giá tính bền vững (robustness) của một hệ thống điều khiển được kết nối mạng (NeCS). Trong thời gian cho phép, chỉ nghiên cứu thuật toán về tính đồng thuận “consensus” cho việc sử dụng phương pháp tối ưu hoá để tính ra những thông số, được sử dụng để đánh giá tính bền vững của mạng lưới. 1.3 Mục tiêu đề tài 1. Kết hợp giữa thuật toán đồng thuận và phương pháp tối ưu hóa để đề xuất ra phương pháp đánh giá độ bền vững của mạng lưới 1.4 Đối tượng nghiên cứu Ứng dụng của tính đồng thuận trong việc đánh giá tính bền vững của mạng lưới. 1.5 Phạm vi nghiên cứu Trong thời gian cho phép, chỉ nghiên cứu thuật toán về tính đồng thuận “consensus” cho việc sử dụng phương pháp tối ưu hoá để tính ra những thong số, được sử dụng để đánh giá tính bền vững của mạng lưới. 1.6 Cách tiếp cận và phương pháp nghiên cứu 1.6.1 Cách tiếp cận Trước đây, đã có những nghiên cứu đánh giá về tính bền vững của mạng lưới dựa vào các giá trị riêng (eigenvalues) của ma trận Laplacian. Trong đề tài này, chúng tôi cũng sử dụng các giá trị riêng để đánh giá tính bền vững của mạng lưới. Vấn đề đặt ra là làm thế nào để tìm ra những giá trị riêng này. Trên thực tế có rất nhiều phương pháp: • Phương pháp “Power iteration” để tính ra giá trị riêng nhỏ nhất khác 0. • Phương pháp “Fast Fourier Transform” để tính toàn bộ các giá trị riêng. • Phương pháp đại số sử dụng tính quan sát được của mạng lưới để tính toàn bộ các giá trị riêng cũng như vector riêng (eigenvectors) của ma trận Laplacian. Vì vậy, chúng tôi lựa chọn một cách tiệp cận hoàn toàn mới sử dụng phương pháp tối ưu hoá (opti- mization) để tìm ra các giá trị riêng của ma trận Laplacian. 1.6.2 Phương pháp nghiên cứu • Nghiên cứu về các thuật toán optimization, 1.6. Cách tiếp cận và phương pháp nghiên cứu 3 • Liên hệ với vấn đề đặt ra để tìm ra cost function phù hợp với thuật toán optimization cũng như các ràng buộc (constraints), • Tìm phương pháp để giải quyết vấn đề đã được đặt ra. 5 Chương 2 Tổng quan về thuật toán “Consensus” 2.1 Lý thuyết đồ thị Sự tương tác qua lại giữa các đối tượng trong mạng lưới được mô hình hóa bằng một đồ thị như Hình 2.1 HÌNH 2.1: Đồ thị G(V,E) Ta kí hiệu: ( 1, nếu (i, j) ∈ E • A ma trận kề của đồ thị với phần tử ma trận ai, j = 0, khác ( N ∑k=1,k6=i ai,k, nếu i = j • L ma trận Laplacian với phần tử li, j = −ai, j, nếu i 6= j • D ma trận độ của độ thị có độ của nút di,i ∈ V nằm trên đường chéo và còn lại là 0. 2.2 Thuật toán đồng thuận Vấn đề đồng thuận trong mạng lưới các đối tượng tự động thường được đầu tư trong nhiều lĩnh vực bao gồm khoa học máy tính và kĩ thuật. Những mạng lưới như vậy, tùy theo những quy luật ưu tiên, hay còn gọi là giao thức, mỗi nút cập nhật tỉ số của mình dựa vào thông tin nhận từ hàng xóm của nó với mục đích là đạt đến sự thống nhất tại một giá trị chung. Nếu giá trị chung này tương ứng với trung bình của các giá trịnh ban đầu, ta gọi sự đồng thuận trung bình. Ví dụ 1. Cho 1 mạng lưới bất kì gồm 5 đối tượng truyền thông với nhau như Hình 2.2 Mỗi nút có một giá trị ban đầu. Giao thức đồng thuận là luật tương tác sao cho thông tin được trao đổi giữa các đối tượng và tất cả hàng xóm của nó trên mạng lưới nhằm đạt đến sự thống nhất trên một đại lượng nhất định, nó phụ thuộc vào trạng thái của tất cả các đối tượng. 6 Chương 2. Tổng quan về thuật toán “Consensus” HÌNH 2.2: (a) điều kiện ban đầu, (b) trạng thái xác lập 2.2.1 Phân loại thuật toán đồng thuận 2.2.2 Định nghĩa Đối với hệ rời rạc và hệ tuyến tính. Cho một đồ thị G(V,E) cho trước, mỗi nút có một giá trị xi là trạng thái của nút i. Gọi x(0) = T [x1(0) x2(0) ...xN(0)] là vector của các trạng thái ban đầu của một mạng lưới cho trước. với mỗi trạng thái bạn đầu cho trước tại mỗi nút xi(0),i ∈ V, nhiệm vụ chính là tính toán giá trị đồng thuận cuối cùng sử dụng bước lặp tuyến tính phân tán. Mỗi bước lặp liên quan đến sự truyền thông cục bộ giữa các nút. 1. Hệ thống thời gian rời rạc. Phương trình cập nhật đồng thuận dựa vào bước lặp tuyến tính: xi(k + 1) = wii(k)xi(k) + ∑ wi j(k)x j(k),i = 1,2,...,N (2.1) j∈Ni Ở dạng Ma trận: x(k + 1) = W(k)x(k),wi j(k) = 0,nếu (i, j) ∈/ E, ∑ wi j(k) = 1 (2.2) j∈Ni∪{i} Hệ thống được gọi là đồng thuận phân tán tiệm cận nếu limk→∞ x(k) = µ1, nghĩa là tất cả các 1 N nút đồng nhất tại một giá trị µ. Khi µ là trung bình các các giá trị ban đầu, µ = N ∑i=1 xi(0), hệ thống được gọi là dạt đế đồng thuận trung bình, nghĩa là: 1 lim Wk = 11T (2.3) k→∞ N 2. Vấn đề đồng thuận trong thời gian hữu hạn. Các hệ thống phức tạp trên thực tế, thời gian thực thi càng trở thành nhân tố quyết định. Chính vì vậu, mục đích của ta bây giờ là thiết kế thuật toán đồng thuận trung bình trong thời gian hữu hạn cho phép tất cả các nút đạt đến giá trị đồng thuạn trun g bình trong D bước cho giao thức tự cấu hình hóa. 1 x(D) = 11T x(0) (2.4) N Nghĩa là, chúng ta sẽ thiết kế các ma trận đồng thuận W1,W2,...,WD sao cho 1 1 T ∏ Wi = 11 i=D N 7 Chương 3 Phương pháp mới để đánh giá tính bền vững của NeCS 3.1 Độ bền vững của mạng lưới Mục đích của các nghiên cứu về tính bền vững của mạng lưới là tìm một đại lượng đo tính bền vững để đánh giá hoạt động của mạng lưới. Hơn thế nữa, hiểu biết khi nào thì mạng lưới bền vững có thể bảo vệ và nâng cấp các hoạt động của mạng lưới một cách hiệu quả. Bằng cách này, nó con được dùng để thiết kế những mạng lưới mới mà có khả năng hoạt đồng tốt khi đối mặt với lỗi hoặc những tấn công. 3.1.1 Độ phản kháng của đồ thị Giả sử đồ thị được xem như một mạch điển, với cạnh (i, j) tương ứng với điện trở 1 Ohm. Thông thường, độ phản khảng hiệu quả giữa 2 nút của 1 mạng lưới (khi điện áp được đưa vào chúng) có thể tính bằng các phép toán nối tiếp và song song. N 1 R = ∑ Ri j = N ∑ 1≤i< j≤N i=2 λi(L) Ghi chú 1. R càng nhỏ, đồ thì càng bền vững. 3.2 Đánh giá tính bền vững của mạng lưới theo hình thức phân tán Như vậy, để tính được những thông số này, ta phải có thông tin về phổ của ma trận Laplacian sp(L) của mạng lưới đó. Ưu điểm của phương pháp này là nó có thể làm việc được với cả mạng lưới kết nối và không kết nối. Giá trị riêng nhỏ thứ 2 λ2(L), là thông số quyết định đến khả năng hoạt động và tính bền vững của một hệ thống tùy và vai trò của độ kết nối của đồ thì biểu diễn cho mạng lưới đó. Cho đồ thị G(V,E) biểu diễn cho mạng lưới có N nút, và có E cạnh. Ta biết sp(L) = {λ1,λ2,...,λN}. Trong đó, các giá trị λi có thể trùng nhau. Vì vậy, chúng ta đề xuất một phương pháp để tính những giá trị riêng khác nhau của phổ sp(L): {λ2,λ3,...,λD+1}. Rồi sau đó, chúng ta lại tính tiếp trị số lặp lại của những giá trị riêng này, từ đó ta có được đầy đủ phổ sp(L). Để tìm được những giá trị riêng khác biệt này, ta có thể áp dụng thuật toán đồng thuận. Như vậy, mỗi một nút trên mạng lưới sẽ có trạng thái ban đầu xi(0),i = 1,2,...,N. Như vậy ta có phương trình cập nhật đồng thuận: k x(k + 1) = (IN − αL)x(k) = (IN − αL) x(0) 11T Gọi x¯ là giá trị trung bình của các giá trị ban đầu, nghĩa là: x¯ = x¯1 = N x(0). Áp dụng thuật toán đồng thuận ta có thể tính được các giá trị riêng khác biệt {λ2,λ3,...,λD+1} của ma trận L. 8 Chương 3. Phương pháp mới để đánh giá tính bền vững của NeCS Định lý 1. Cho một đồ thị kết nối với ma trận Laplacian L và những giá trị riêng khác nhau khác 0 {λ2,λ3,...,λD+1}. Giả sử giá trị cục bộ của vector x(0) không vuông góc với bất vì vector riêng nào của ma trận Laplacian, ta có hàm mục tiêu: 1 2 k 2 E(α) = kx(h) − x¯k = k ∏(IN − αL) x(0) − x¯k k=h T 1 1 với α = (α1 α2 ...αh) ,h ≥ D là nhỏ nhất khi và chỉ khi { ,..., } ⊆ {α1,α2,...,αh} λ2 λD+1 Như vậy, việc ta cần làm là tìm một phương pháp tối ưu hóa để giải quyết vấn đề trên. Ý tưởng của phương pháp được đề xuất là tối thiểu hóa sự bất đồng thuận giữa các hàng xóm với nhau về giá trị của αk trong khi đảm bảo rằng sự phân tố của ma trận trung bình đạt đến được. Sự phân tố này được đánh giá bằng cách ràng buộc các giá trị của các nút sau h bước của thuật toán đồng thuận để được bằng giá trị trung bình của các giá trị ban đầu. Ta có hàm mục tiêu như sau: 1 h 2 min ∑ ∑i∈V ∑ j∈N (α j,k − αi,k) (3.1) N×1 2 k=1 i αk∈R ,k=1,2,...,h subject to x(h) = x¯ (3.2) hoặc tương đương với, 1 h min ∑ αkLαk (3.3) N×1 2 k=1 αk∈R ,k=1,2,...,h subject to x(h) = x¯ (3.4) Sau khi chúng ta tìm được các giá trị riêng khác không của ma trận L, việc cần làm tiếp theo là chúng ta tìm được bội số của những giá trị riêng này để tạo thành một quang phổ của ma trận L như đã trình bày ở trên. Phương pháp tìm những bội số mi này được trình bày như trong dự luật sau đây: Dự luật 1. Xem xét một đồ thị vô hướng được kết nối với trình tự về độ {di} và ma trận Laplacian L. D Gọi Λ ∈ ℜ là vector của những nghịch đảo của các nghiệm của đa thức P(c0,c1,··· ,cD;·) của độ D nhỏ nhất sao cho JN = P(c0,c1,··· ,cD;L) và m ∈ N là đáp án của quy hoạch tuyến tính sau: min ΛT m, (3.5) m∈ℜD N T T s.t. 1 m = N − 1; Λ m = ∑ di; m ≥ 1 (M ) i=1 D m ∈ N . Vấn đề (3.5) có thể được giải quyết hiệu quả bằng cách sử dụng phương pháp Branch-and-Bound Chinneck, 2012. 9 Chương 4 Phương pháp tối ưu hoá đánh giá tính bền vững 4.1 Tính toán các giá trị riêng của ma trận Laplacian riêng biệt Gọi P(c0,c1,··· ,cN−1;·) là một đa thức sao cho JN = P(c0,c1,··· ,cN−1;L) được xác định như sau: 1 T Với JN = N 11 là ma trận trung bình, nó có thể được viết dưới dạng một đa thức của ma trận Laplacian như sau: h h t JN = P(c0,c1,··· ,cN−1;L) = ∑ ct L = ∏(I − αiL) t=0 i=1 với  1, if t = 0.  t ct = (−1) ∑i< j<···<t αiα j ···αt , if t = 1,...,h − 1. (4.1)  h h (−1) ∏i=1 αi, if t = h. h Sự hệ số hóa của ma trận trung bình JN = ∏i=1(I − αiL) là nhỏ nhất khi và chỉ khi {αi} là nghich đảo của D giá trị riêng khác không của ma trận Laplacian, Kibangou, 2012. Chúng ta có: N−1 x¯ = JNx(0) = ∑ ct q(t) = Qc, (4.2) t=0 N×N 1 t với Q = (q(0) q(1) ··· q(N − 1)) ∈ ℜ và q(t) = α (x(t) − x(t + 1)) = L x(0). Chú ý rằng Q là một ma trận hạ bậc, trừ khi tất cả các giá trị riêng của ma trận Laplacian là riêng biệt. Vì vậy, tồn tại nhiều đáp án sao cho Qc = x¯. Một trong số đó, đáp án bình phương nhỏ nhất tìm được bằng cách giải vấn đề sau: minkck2 subject to Qc = x¯. (4.3) c các thành tố của đáp áp tìm được c là hệ số của đa thức P(c0,c1,··· ,cN−1;·) mà thừa số hóa ma trận JN. (d +1)×N Trong đề tài này, mỗi nút chủ phải xâm nhập vào các ma trận con Qi ∈ ℜ i tương ứng với sự lựa chọn của các hàng của ma trận Q. Ta thấy rằng rank(Qi) ≤ min(di,D) + 1. Ý tưởng là tính vecto hệ số của đa thức c một cách phân tán. Ta có: N 2 min ci − c j s.t. Qici = x¯1, i = 1,··· ,N, (4.4) ci ∑ ∑ i=1 j∈Ni với ci là giá trị cục bộ của c. Vấn đề này có thể được giải một cách hiệu quả nếu các ma trận Qi đều là các ma trận có hạng toàn hàng và nếu giá trị trung bình x¯ được biết trước. Cách tiếp cận này đã được sử dụng ở Tran and Kibangou, 2013 và Tran and Kibangou, 2014. Giả thiết rằng N dữ liệu đo được đầu tiên của giao thức đồng thuận của mạng lưới ban đầu được sử dụng để tính cho cả hệ số và sự hệ 10 Chương 4. Phương pháp tối ưu hoá đánh giá tính bền vững số hóa của ma trận trung bình và giá trị đồng thuận. Chúng ta cũng giả thiết rằng vecto các điều kiện ban đầu x(0) không vuông góc với vector của ma trận L. Bây giờ chúng tôi sẽ đề xuất để giải quyết vấn đề: N N θ 2 1 − θ 2 min ∑ ∑ kci − c jk + ∑(x¯i − xi(0)) , x¯i,ci,i=1,···,N 2 2 i=1 j∈Ni i=1 s.t. Qici = x¯i1, i = 1,...,N, (4.5) với θ là biến số có thể điều chỉnh được (0 ≤ θ ≤ 1) và x¯i sự tính toán cục bộ của giá trị trung bình. Đây là bài toán tối ưu hóa lồi. Cho nên, nó có thể được giải quyết một cách hiệu quả thông qua phương pháp ADMM. ADMM rất dễ thực hiện, và chứng minh về hội tụ của phương pháp đã được nghiên cứu rất kĩ trong nhiều bài báo Erseghe et al., 2011; Boley, 2013; Boyd et al., 2011. Để đạt được thuật toán ADMM cho vấn đề, chúng tôi đưa vào các biến {zi j,µi j}. Vì vậy, vấn đề tối ưu hóa có ràng buộc sau đây tuyệt đối tương đương với vấn đề (4.5): N N θ 2 1 − θ 2 min ∑ ∑ kci − c jk + ∑(x¯i − xi(0)) , x¯i,ci,i=1,···,N 2 2 i=1 j∈Ni i=1 s.t x¯i = µi j, i = 1,...,N, j ∈ Ni. ci = zi j. t zi j = sign(t)zi j, ci ∈ Ci(x¯i). where: ( 1 nếu t là số chẵn, • sign(t) = . −1 nếu t là số lẻ N • Ci(x¯i) là tập hợp các ràng buộc đối với nút i. Nó được xác định như sau: Ci(x¯i) = {c ∈ ℜ | Qic = x¯i1}. Bây giờ, đưa thêm vào vài biến nữa: υ và y, biểu thức Lagrange là: Lρ1ρ2 (x¯,c,µ,z,υ,y) = Lρ1 (c,z,y) + Lρ2 (x¯,µ,υ). với: θ N ρ L (c,z,y) = kc − c k2 + 1 kc − z k2 ρ1 2 ∑ ∑ i j ∑ 2 i j i=1 j∈Ni j∈Ni T + ∑ yi j(ci − zi j), j∈Ni 1 − θ N ρ L (x¯,µ,υ) = (x¯ − x (0))2 + 2 (x¯ − µ )2 ρ2 2 ∑ i i ∑ 2 i i j i=1 j∈Ni + ∑ υi j(x¯i − µi j), j∈Ni với ρ1,ρ2 là hệ số điều chỉnh, hằng số. ADMM cung cấp các đáp án theo cách lặp lại theo 5 bước sau: • Tối thiểu hóa với giá trị trung bình x¯i x¯i[k + 1] = argmin Lρ2 (x¯i[k],µi j[k],υi j[k]). (4.6) 4.1. Tính toán các giá trị riêng của ma trận Laplacian riêng biệt 11 • Tối thiểu hóa đối với hệ số đa thức ci: cˆi = argmin Lρ1 (ci[k],zi j[k],yi j[k]), (4.7) ci[k + 1] = ΩCi(x¯i[k+1])[cˆi] (4.8) với ΩCi(x¯i[k+1])[·] là hình chiếu lên tập hợp các ràng buộc Ci(x¯i[k + 1]) của vector. • Tối thiểu hóa đối với biến phụ µi j với ràng buộc là µ ji = µi j: µi j[k + 1] = argmin Lρ2 (x¯i[k + 1],µi j[k],υi j[k]). (4.9) • Tối thiểu hóa đối với biến phụ zi j: zi j[k + 1] = argmin Lρ1 (ci[k + 1],zi j[k],yi j[k]). (4.10) • Cập nhập hệ số Lagrange : υi j[k + 1] = υi j[k] + ρ2(x¯i[k + 1] − µi j[k + 1]). (4.11) yi j[k + 1] = yi j[k] + ρ1(ci[k + 1] − zi j[k + 1]). (4.12) Giải các bài toán tối ưu hóa con (4.6) và (4.7), ta được: (1 − θ)xi(0) + ρ2 ∑ j∈Ni µi j[k] − ∑ j∈Ni υi j[k] x¯i[k + 1] = , (4.13) 1 − θ + ρ2di θ∑ j∈Ni c j + ρ1 ∑ j∈Ni zi j − ∑ j∈Ni yi j cˆi = , respectively. di(θ + ρ1) Sau đó, đối chiếu kết quả đạt được với ràng buộc ci[k + 1] = ΩCi(x¯i[k+1])[cˆi[k + 1]]. vì rang buộc là tuyến tính nên ta có thể áp dụng phương trình sau để tìm nghiệm ci[k + 1]: ci[k + 1] = x¯i[k + 1]Q˜ i1 + (IN − Q˜ iQi)cˆi[k + 1], (4.14) ˜ T T −1 với Qi = Qi (QiQi ) . Tiếp theo, giải các bài toán tối ưu hóa con (4.9) và (4.10), thu được x¯i[k + 1] + x¯j[k + 1] υi j[k] + υ ji[k] µi j[k + 1] = + , (4.15) 2 2ρ2 1 zi j[k + 1] = ci[k + 1] + yi j[k], respectively. (4.16) ρ1 Sau đó, ta đối chiếu zi j[k + 1] với ràng buộc về dấu: ( max(0,zt [k + 1]) if mod(t,2) = 0. zt [k + ] = i j i j 1 t (4.17) min(0,zi j[k + 1]) if mod(t,2) 6= 0. Biến θ cho phép cân đối hai hàm mục tiêu vì hàm ràng buộc Ci(x¯i) phụ thuộc vào giá trị đồng thuận xi. Quy trình tối ưu hóa có thể thiên về vấn đề đồng thuận nhiều hơn. Với mục đích này, thay vì ta để 12 Chương 4. Phương pháp tối ưu hoá đánh giá tính bền vững biến θ không đổi, ta sẽ chọn biến θ(k) thay đổi theo quy luật 1 − e−βk θ(k) = (0 < β < 1) (4.18) 1 + e−βk để giữ nó trong khoảng [0,1] và để đề cảo tầm quan trọng của việc thừa số hóa trong khi giảm sự tập trung vào đồng thuận trung bình. 4.2 Tính toán các giá trị riêng từ ma trận đồng thuận trung bình Gọi Pi(c0,c1,··· ,cN;·) là đa thức được xây dựng bằng các hệ số ci tìm được từ thuật toán. Bằng cách lấy nghịch đảo của nghiệm của đa thức trên Pi(c0,c1,··· ,cN;·), ta thu được một tập hợp các giá trị mà có chứa D các giá trị riêng khác không của ma trận Laplacian. Mục tiêu của chúng ta là tìm tập hợp con nhỏ nhất của các nghiệm của Pi(c0,c1,··· ,cN;·) sao cho sự hệ số hóa của ma trận trung bình vẫn N−1 còn tồn tại. Nghĩa là JN = Pi(c0,c1,··· ,cN;L) hay x¯i = ∑ ct qi(t). Chúng ta đặt ra dự luật sau: t=0
Dự luật 2. Let Qi = Qi,N−1 qi(N − 1) là vector của các giá trị đo lường tức thời (quá độ) và c vector mà Qic = x¯1. Ta gọi S là tập hợp các nghiệm {αi} của đa thức bậc N với vector các hệ số c. Gọi c˜αi đa thức bậc (N −1) với các nghiệm trong S\{αi}. Sau đó tập hợp của D giá trị riêng của ma trận Laplacian được tìm thấy bởi  1  Λ = |Qi,N−1c˜αi 6= x¯1, αi ∈ S . αi Proof: Đây là một quá trịnh loại bỏ từng nghiệm một cho đến khi sự hệ số hóa còn tồn tại . 13 Chương 5 Mô phỏng bằng Matlab Trong chương này, tác giả nghiên cứu một mạng lưới nhỏ Microgrid, gồm 6 DG như trong Hình 5.1a, trong đó, những DG này tương tác với nhau như một đồ thị, như trong Hình 5.1b. B2 B7   L1 B6 L2 B3 B5 B1 B4 DG1 DG3 DG5 L3 L4 L5 B9 B10 B11 B8 DG2 DG4 DG6 Communication Link B12 L9 Main Grid L8 (B) Mạng lưới biểu diễn sự tương tác L7 B13 giữa 6 DG trong lưới điện này L6 B14 L10 B15 L11 L12 (A) Đồ thị của một mạng lưới nhỏ MG, gồm 6 DGs. HÌNH 5.1: Một lưới điện nhỏ với 6 DG Các thông số của mỗi DG được trình bày trong Bảng 5.1. BẢNG 5.1: Thông số của các DGs DG1 DG2 DG3 DG4 DG5 DG6 Pmax (kW) 10 25 20 30 5 10 DGi max Pload (kW) 80 Trong đó Pmax,Pmax lần lượt là công suất thực cực đại của mỗi DG i và công suất tổng cực đại của DGi load tải. Như trình bày ở các chương trước, quy trình được đề xuất làm nhiệm vuh dự đoán cho bất kỳ chiến lược điều khiển hợp tác được ứng dụng trong lưới điện nhỏ này. Trước khi bắt đầu bất kì một thao tác nào, chúng ta lấy thông tin từ những DG để chạy quy trình được đề xuất trước để đánh giả hiệu suất của lưới điện nhỏ này. 14 Chương 5. Mô phỏng bằng Matlab Thu thập những dữ liệu ban đầu của công suất PDGi tại mỗi DG để xác định thông tin ban đầu tại PDGi thời điểm t = 0: xi(0) = Pmax , vì vậy x[0] = {0.84,0.76,0.6,0.1667,0.53,0.46}. DGi Bây giờ, chúng ta bắt đầu thực nghiệm với 4 trường hợp của cấu trúc mạng lưới để thấy được sự khác nhau của các chỉ số bền vững. 5.1 Sơ đồ kết nối gốc Trong bài báo Tran and Kibangou, 2015, các tác giả đã thực hiện so sánh giữa phương pháp ADMM và 2 phương pháp khác để rút ra kết luận rằng phương pháp ADMM là phương pháp nhanh nhất. Vì vậy, trong chương này, chúng tôi chỉ chú trọng vào khả năng hoạt động của chu trình được đề xuất và sự lựa chọn giá trị của γ để đạt đến giải pháp tốt nhất. Tập hợp các giá trị riêng Laplacian riêng biệt là Λ = {2,4,6} và chúng tôi sẽ so sánh với kết quả của thuật toán để kiểm chứng các thuật toán. Tùy theo Thuật toán, các DG phải đạt được sự thống nhất cùng m