Báo cáo Tóm tắt 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)

ĐẠI HỌC ĐÀ NẴNG QUỸ PHÁT TRIỂN KH&CN BÁO CÁO TÓM TẮT ĐỀ TÀI KHOA HỌC VÀ CÔNG NGHỆ CẤP ĐẠI HỌC ĐÀ NẴNG 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) Mã số: B2016-ĐN02-03 Chủ nhiệm đề tài: TS. TRẦN THỊ MINH DUNG Đà Nẵng, tháng 02/2019 EAI Hec oaNANc euY psAr rnrBx xnc'bN nAo cAo roNG KET of rer KIroA HQC ve cOxc NGHF cAr o4r HQC oa NANc xAv ognc rnudr foAry rOI tlu oANn 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 ---,rlta /l'tttp-'' TrAn ThiMinh Dung POS. TS. LE MI KM OANH 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 "hi t6n t4i trong khoa hgc m6y tinir, cfing nhu trong khoa 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 Chfr nhiQm ad tai (lry, hp vd t€n) "5- , h** ---Ty'tt '' Tr,in Thi Minh Dung T6 chfc chfr tri 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 iMụ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 NeCS 7 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ững 9 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 vDanh 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 ofMultipliersMethod MSE Mean Square Error FFT Fast Fourier Transform NECs Networked Control Systems DG Distributed Generation 1Chươ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. 5Chươ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: • A ma trận kề của đồ thị với phần tử ma trận ai, j = { 1, nếu (i, j) ∈ E 0, khác • L ma trận Laplacian với phần tử li, j = { ∑Nk=1,k 6=i ai,k, nếu i= 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) = [x1(0) x2(0) . . .xN(0)]T 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)+ ∑ j∈Ni wi j(k)x j(k), i= 1,2, . . . ,N (2.1) Ở dạng Ma trận: x(k+1) =W(k)x(k),wi j(k) = 0,nếu (i, j) /∈ E, ∑ j∈Ni∪{i} wi j(k) = 1 (2.2) 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 nút đồng nhất tại một giá trị µ. Khi µ là trung bình các các giá trị ban đầu, µ= 1N ∑ N i=1 xi(0), hệ thống được gọi là dạt đế đồng thuận trung bình, nghĩa là: lim k→∞ Wk = 1 N 11T (2.3) 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. x(D) = 1 N 11Tx(0) (2.4) Nghĩa là, chúng ta sẽ thiết kế các ma trận đồng thuậnW1,W2, . . . ,WD sao cho 1 ∏ i=D Wi = 1 N 11T 7Chươ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. R = ∑ 1≤i< j≤N Ri j = N N ∑ i=2 1 λ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: x(k+1) = (IN−αL)x(k) = (IN−αL)kx(0) Gọi x¯ là giá trị trung bình của các giá trị ban đầu, nghĩa là: x¯= x¯1= 11 T 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 đồ