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.
33 trang |
Chia sẻ: Trịnh Thiết | Ngày: 06/04/2024 | Lượt xem: 152 | Lượt tải: 0
Bạn đang xem trước 20 trang tài liệu 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), để xem tài liệu hoàn chỉnh bạn click vào nút DOWNLOAD ở trên
ĐẠ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 đồ