Đề xuất phương pháp ước lượng độ tin cậy mạng manet dựa trên kỹ thuật phân cụm và dự phòng mạng

vụ truyền nhận dữ liệu vừa đảm 
bảo nhiệm vụ chuyển tiếp do đó tại từng thời điểm mỗ nút mạng có vai trò khác nhau, vai trò này nó thay đổi liên tục 
theo thời gian. Nhƣ nhóm tác giả [3] đề xuất hƣớng tiếp cận “không-thời gian” cho tối ƣu vùng phủ của mạng nhằm 
giải quyết cả hai yếu tố là tính phi cấu trúc của mạng và tính đa nhiệm của nút mạng. 
Theo [4] đề xuất hƣớng tiếp cận khi tính độ tin cậy của mạng cảm biến không dây di động (MANET) dựa trên 
việc mô hình hóa cấu trúc của mạng tại từng thời điểm đang xét dƣới dạng đồ thị rồi dựa trên cấu trúc đó để tính ra độ 
tin cậy của mạng, về cơ bản phƣơng pháp này dựa trên hai tham số chính là: độ tin cậy của từng nút và độ tin cậy của 
liên kết giữa các nút theo cấu trúc của mạng. 
B. Tính độ tin cậy dựa trên việc phân cụm mạng 
 Thời gian hoạt động không lỗi của các nút mạng là đại lƣợng đặc trƣng cho khả năng không lỗi của nó trong 
khoảng thời gian t. Độ tin cậy P(t): của phần tử hoặc của hệ thống là xác suất để trong suốt khoảng thời gian khảo sát t, 
phần tử đó hoặc hệ thống đó vận hành an toàn [1]. 
 Từ đặc điểm của mạng đặt ra nhiều thách thức trong tính toán đánh giá độ tin cậy của mạng, một trong những 
phƣơng pháp đang đƣợc nhiều nghiên cứu lựa chọn hiện nay là phân chia mạng thành các phân cụm nhỏ và trên các 
phân cụm này sẽ tiến hành tính toán và đánh giá từng phân cụm rồi tiến đến đánh giá toàn mạng dựa trên mối quan hệ 
giữa các phân cụm với nhau. 
II. PHÂN CỤM MẠNG 
A. Phân cụm mạng đồng nhất 
 Các tác giả [2, 5, 6] đã chia mạng MANET thành các phân cụm (cluster) mạng và dựa trên các phân cụm này 
để tính độ tin cậy của toàn mạng, gọi C là tập các phân cụm khi đó ta có: 
 { } với β là số phân cụm trong mạng. (1) 
 Với phƣơng pháp phân cụm nhƣ trên sẽ giảm độ phức tạp của cấu hình mạng, giả sử xét một mạng MANET 
với α nút thì khi đó số lƣợng cấu hình có thể có của mạng sẽ là ( ( cấu hình. Giả sử mạng MANET nhƣ 
Lê Khánh Dƣơng, Lê Quang Minh, Nguyễn Anh Chuyên, Tô Hữu Nguyên 113 
trong hình 1 (24 nút mạng) ta có số lƣợng cấu hình có thể có là ( ( trong khi nếu sử dụng 
phƣơng pháp phân cụm thì có C sẽ nhỏ hơn rất nhiều và độ tin cậy của toàn mạng sẽ không phụ thuộc vào từng cấu 
hình cụ thể của từng phân cụm cũng nhƣ việc tính toán trở nên đơn giản hơn. 
Hình 1. Phân cụm mạng MANET 
 Với S định nghĩa là tập cấu hình hệ thống: 
 ⋃ 
 (2) 
 Đặt là độ tin cậy của phân cụm Ci, khi đó độ tin cậy của toàn mạng sẽ là: 
 ( ∏ 
 (3) 
 Nếu mạng là chia đều và đồng nhất thì công thức (3) sẽ thành lý tƣởng là: 
 ( 
 (4) 
B. Phân bố nút mạng trong phân cụm 
 Theo [7], giả sử các nút mạng đƣợc phân bố ngẫu nhiên trong một vùng mạng diện tích Ω, xét một kịch bản 
mạng hình lƣới có các nút đƣợc phân bố nhƣ một quá trình Poisson hai chiều với mật độ  trong mặt phẳng. Xác suất 
để tìm thấy k nút trong một miền diện tích Ω là: 
( 
 ( (5) 
III. ƢỚC LƢỢNG ĐỘ TIN CẬY CỦA PHÂN CỤM MẠNG CÓ SỬ DỤNG NÚT CH 
A. Nút CH 
 Trong MANET, khi chia mạng thành S phần nhƣ công thức (2); với mỗi phân cụm định nghĩa một head 
node (clusterhead node-CH node) đƣợc ký hiệu là h(c) của phân cụm phải là một nút mà khoảng cách của nó đến các 
nút còn lại trong phân cụm phải nhỏ hơn hoặc bằng bán kính truyền dẫn r của nút đó [6], tức là: 
 ( ( (6) 
Hình 2. Phân cụm sử dụng nút CH 
114 ĐỀ XUẤT PHƢƠNG PHÁP ƢỚC LƢỢNG ĐỘ TIN CẬY MẠNG MANET DỰA TRÊN KỸ THUẬT PHÂN CỤM VÀ DỰ PHÒNG MẠNG 
 Nút CH yêu cầu có nguồn năng lƣợng cao hơn các nút còn lại trong mạng bởi khi tổ chức theo phân cụm, mỗi 
khi một nút CH hết năng lƣợng hay ra khỏi vùng (địa lý) của một phân cụm thì sẽ kích hoạt một hoạt động “phân cụm 
lại” (reclustering) của toàn bộ các nút trong phân cụm, bản thân hành động phân cụm lại này đòi hỏi tiêu tốn một năng 
lƣợng không nhỏ, do đó độ tin cậy của phân cụm phần nhiều phụ thuộc vào độ tin cậy của những nút CH này [6]. 
 Với việc sử dụng các nút CH này đảm bảo các nút thành viên trong phân cụm luôn trong phạm vi truyền của 
CH, mỗi khi nó di chuyển ra khỏi phân cụm và ra nhập phân cụm khác vẫn không kích hoạt hoạt động “phân cụm lại” 
toàn bộ mạng bởi khi đó chỉ là việc xử lý tại các nút CH của mỗi phân cụm có biến động về cấu trúc mạng (khi thêm, 
bớt thành viên). 
B. Ước lượng độ tin cậy của phân cụm có CH node 
 Theo nhóm các tác giả [3, 5, 6] việc lựa chọn một nút làm Nút CH dựa trên nguồn năng lƣợng còn lại của một 
nút so với tổng năng lƣợng trung bình của các nút trong nhóm, việc lựa chọn theo tiêu chí này đảm bảo nút CH là nút 
có năng lƣợng lớn hơn các nút còn lại trong nhóm và đảm bảo cấu trúc của nhóm xoay quanh nút CH đƣợc duy trì lâu 
hơn, tuy nhiên việc lựa chọn theo hƣớng này có những hạn chế nhất định nhƣ: độ tin cậy của một nút khi đặt trong vấn 
đề truyền thông không hoàn toàn phụ thuộc vào mức năng lƣợng hiện có của nút đó, bởi lẽ với một nút còn rất ít năng 
lƣợng (ví dụ còn dƣới 5% năng lƣợng) nhƣng ở vị trí kết nối thuận lợi thì hoạt động truyền thông nội nhóm vẫn đảm 
bảo tốt thì sẽ có độ tin cậy cao hơn nhiều so với một nút CH có nhiều năng lƣợng nhƣng ở vị trí không thuận lợi cho 
các nút trong nhóm truyền thông cho nhau. Ngoài ra các công thức tính toán năng lƣợng suy hao trong truyền thông 
đều dựa trên khoảng cách giữa nút gửi và nút nhận. 
 Do đó trong bài báo này xác định việc chọn một nút CH cho một nhóm dựa trên vị trí của nút đó sao cho 
“thuận lợi nhất” trong liên kết nội nhóm, đề xuất phƣơng án dự phòng cho nút CH theo phƣơng án dự phòng lạnh [1] 
(hình 3). 
Hình 3. Sử dụng nút dự phòng trong phân cụm 
Mệnh đề: cho một phân cụm có n nút, phân cụm gọi là hoạt động (trong trƣờng hợp này không tính đến liên kết nội 
nhóm của cụm) khi có tối thiểu k (0<k≤n) nút hoạt động, giả sử các nút mạng là đồng nhất và có độ tin cậy là p(t). Khi 
đó độ tin cậy PC(t) của phân cụm (với tối thiểu k nút hoạt động) sẽ là: 
 ( ∑ 
 ( ( ( (7) 
Chứng minh: Xét trƣờng hợp cụm có n nút hoạt động thì độ tin cậy của cụm sẽ là ( ( 
, trong trƣờng hợp có 
01 nút bị hỏng thì độ tin cậy của cụm sẽ là ( 
 ( ( ( , trong trƣờng hợp 02 nút hỏng ta có 
 ( 
 ( ( ( , trong trƣờng hợp n-k nút hỏng (có k nút còn hoạt động) ( 
 ( ( ( . 
 Xét một phân cụm có sử dụng nút CH (độ tin cậy của nút CH này là 
( , giả sử phân cụm có n nút mạng 
đồng nhất, phân cụm chỉ đƣợc coi là hoạt động khi có k nút hoạt động (mệnh đề) và nút CH node hoạt động. Vậy độ tin 
cậy của phân cụm sẽ là: 
 ( ( ( 
 (8) 
C. Nâng cao độ tin cậy của phân cụm dựa trên dự phòng cho nút CH 
 Trong mỗi phân cụm nút CH có vai trò rất quan trọng, nó đƣợc coi là nút điều khiển của cả phân cụm, trong 
các mạng cảm biến không dây việc chọn một nút làm nút CH có thể dựa trên khoảng cách của nút đó với các nút còn 
lại hay dựa trên nguồn năng lƣợng còn lại của nó so với các nút còn lại trong phân cụm, trong phạm vi bài báo này 
chúng tôi không đề cập đến vị trí hay nguồn năng lƣợng hiện có của một nút CH, bài báo tập trung giải quyết phƣơng 
Lê Khánh Dƣơng, Lê Quang Minh, Nguyễn Anh Chuyên, Tô Hữu Nguyên 115 
án dự lấy m nút (n-m>k) bất kỳ xung quanh nút CH làm nút dự phòng với một rằng buộc là nó thỏa mãn công thức (6), 
nhằm nâng cao độ tin cậy của nút CH, dự phòng cho nút CH có 02 phƣơng án dự phòng là [1]: 
 Dự phòng nóng: là các nút làm dự phòng hoạt động đồng bộ với thành phần đƣợc dự phòng và sẵn sàng thay 
thế bất cứ lúc nào khi thành phần dự phòng bị lỗi. 
 Dự phòng lạnh: là các nút làm dự phòng không đƣợc sử dụng cho đến khi thành phần đƣợc dự phòng bị lỗi 
cần đƣợc thay thế, nó sẽ phù hợp với những nút mạng có nguồn ngăn lƣợng hạn chế. 
 Trong trƣờng hợp này sử dụng phƣơng án dự phòng lạnh, tức là các nút làm dự phòng sẽ không hoạt động cho 
đến khi nút CH bị lỗi thì nó sẽ chuyển sang giữ vai trò là nút CH. 
 Sau đây sẽ tính đến độ tin cậy của phân cụm trong các trƣờng hợp lần lƣợt có 1 nút, 2 nút, 3 nút làm dự phòng 
lạnh [1] cho nút CH, có tính đến yêu cầu tối thiểu có k nút hoạt động nhƣ nêu trong mệnh đề ở trên, từ công thức (5), 
(6), (7) và (8) suy ra: 
 Nút CH có 01 nút dự phòng: 
 ( 
(
( 
 ( ) ( ( ( 
 ( ( ( 
 ( ( ( 
 ( 
 ( ( (
( 
 ( ) ( ( ( 
 ∑ 
 ( ( ( ) 
 (9) 
 Nút CH có 02 nút dự phòng: 
 ( 
(
( 
 ( ) ( ( 
 ( ( ( ( ( 
 ( ( ( 
 ( 
 ( ( (
( 
 ( ) ( ( 
 ( ( ) ( ) ( ( 
 ∑ 
 ( 
 ( ( ) (10) 
 Nút CH có 03 nút dự phòng: 
 ( (
( 
 ( ) ( ( 
 ( ( ( 
 ( ( 
 ( ( ( 
 ( ( ( 
 ( ( ( 
(
( 
 ( ) ( ( 
 ( ( ( 
 ( ( 
 ( ( ( 
 ∑ 
 ( 
 ( ( ) (11) 
Với Ω trong trường hợp này trùng với miền truyền dữ liệu của các nút CH (và các nút được chọn là dự phòng). 
IV. PHƢƠNG ÁN DỰ PHÒNG SỬ DỤNG PHÂN CỤM LÕI 
A. Phân cụm lõi 
 Xét mạng MANET có N nút cảm biến đƣợc phân thành β phân cụm với mỗi cụm có α nút mạng (N=β*α). Đặc 
điểm của các nút trong mạng MANET vừa là nút nhận và gửi tin cũng đồng thời là nút chuyển tiếp (router) trong 
mạng. Vì vậy các nút ở trung tâm của mạng sẽ có xác suất làm router cao hơn các nút ở vùng biên, do đó ảnh hƣởng rất 
lớn đến khả năng kết nối và truyền tin thành công trong mạng, đây cũng là nút sẽ tốn nhiều năng lƣợng trong thời gian 
hoạt động của nó vì tất cả các truyền thông giữa các nút ở các vùng biên xa nhau đều đi qua các nút trung gian ở vùng 
trung tâm (hình 4) [4]. Vấn đề đặt ra ở đây là trong kỹ thuật phân cụm với những nút ở vùng trung tâm cần có cơ chế 
dự phòng nhằm đảm bảo vùng này có độ tin cậy cao nhất. 
Hình 4. Phân cụm lõi 
116 ĐỀ XUẤT PHƢƠNG PHÁP ƢỚC LƢỢNG ĐỘ TIN CẬY MẠNG MANET DỰA TRÊN KỸ THUẬT PHÂN CỤM VÀ DỰ PHÒNG MẠNG 
B. Tính độ tin cậy của mạng 
 Gọi phân cụm lõi Cb với số nút là α vậy khi đó công thức (3) độ tin cậy của mạng sẽ là: 
 ( ∏ 
 (12) 
 Có nhiều cách để tăng độ tin cậy của phân cụm lõi này, trong bài báo này đề xuất ba cách: 
 Cách thứ nhất: sử dụng 1, 2, 3 nút dự phòng lạnh nhƣ ở các công thức (9), (10), (11) hoặc sử dụng m nút dự phòng 
cho nút CH (3<m<k); ở cách này các nút dự phòng cần đƣợc lựa chọn đảm bảo sao cho thỏa mãn (5) và (6). 
 Cách thứ hai: do là cụm lõi nên ƣu tiên các nút dự phòng cho cụm này, trong cụm này ngoài các nút hoạt động 
bình thƣờng kèm với nó là các nút dự phòng cùng thuộc tính tƣơng tự nó và đƣợc dự phòng theo phƣơng thức 
dự phòng lạnh nhƣ trên [1]. Khi đó số lƣợng nút ở cụm trung tâm Cb sẽ là 2α. 
 Cách thứ ba: tổng hợp cả hai cách trên, tức là ngoài các nút CH đƣợc dự phòng theo cách thứ nhất thì bản thân 
các nút thành viên của phân cụm lõi đƣợc dự phòng theo cách thứ hai. Cách tính độ tin cậy theo cách này suy 
ra từ cách tính của hai cách trên. 
 Tính độ tin cậy của phân cụm lõi theo cách thứ 2, cụm lõi sẽ gồm 2α trong đó có α nút dự phòng cho α nút 
hoạt động, trong bài báo này xét mạng là đồng nhất tức là các nút đều có độ tin cậy là p(t) khi đó có thể coi phân cụm 
lõi gồm α nút với độ tin cậy của mỗi nút là: 
 ( ( ( ( ) ( ( ( (13) 
 Từ hai công thức (8) và (13) ta có: 
 ( ( 
 ( ( ( ( 
 ( (14) 
V. KẾT LUẬN VÀ HƢỚNG NGHIÊN CỨU 
 Trong bài báo này đã trình bày phƣơng pháp tính độ tin cậy cho mạng MANET dựa trên kỹ thuật phân cụm, 
trong đó việc sử dụng hàm tính xác suất tìm thấy k nút mạng trong một miền diện tích Ω làm đại lƣợng đặc trƣng cho 
khả năng kết nối trong nội bộ phân cụm giữa các nút với nhau thông qua nút CH, vừa đảm bảo tính đơn giản của việc 
tính toán độ tin cậy dựa trên cấu hình, vị trí của nút CH cũng nhƣ những nút dự phòng cho nó. 
 Trong bài báo này các phép tính toán đều đƣợc xét trong điều kiện gắn với tham số k (là số nút tối thiểu cần 
thiết để một phân cụm đƣợc coi là hoạt động). Bài báo gợi mở hƣớng hoàn thiện công thức (8) tính độ tin cậy của phân 
cụm mạng có tính đến độ tin cậy của liên kết mạng thông qua “khoảng cách” giữa các nút trong phân cụm là một hàm 
phụ thuộc khoảng cách và năng lƣợng giữa các nút với nút CH trong các phƣơng án dự phòng nhằm đảm bảo nút CH 
có độ tin cậy cao nhất. 
 Hƣớng nghiên cứu tiếp theo của nhóm sẽ tập trung vào tính toán độ tin cậy của liên kết giữa các nút trong 
phân cụm, vấn đề ảnh hƣởng vị trí của các nút đối với năng lƣợng để truyền thông, vấn đề suy hao năng lƣợng trong 
truyền tin giữa các nút và năng lƣợng tiêu hao khi chuyển vùng [8, 9]. Việc đƣa ra đƣợc một mô hình tính độ tin cậy 
của liên kết dựa trên độ phủ vừa đảm bảo giảm sự phụ thuộc vào tính phức tạp rất lớn của cấu hình mạng vừa gắn đƣợc 
với vấn đề năng lƣợng trong tính toán độ tin cậy của bản thân các nút và đây cũng là hƣớng nghiên cứu tiếp theo. 
VI. LỜI CẢM ƠN 
Nhóm tác giả bài báo này bày tỏ lòng cảm ơn đối với Dự án sản phẩm công nghệ cao của Bộ Công thƣơng "Ứng dụng 
công nghệ bảo đảm an ninh, an toàn mạng và bí mật thông tin ở mức cao để phát triển bộ giải pháp an toàn an ninh 
mạng LAN cho cơ quan nhà nƣớc và doanh nghiệp". 
TÀI LIỆU THAM KHẢO 
[1] Lê Khánh Dƣơng, Nguyễn Văn Tảo, Lê Quang Minh, Nguyễn Anh Chuyên, Quách Xuân Trƣởng, “Ảnh hƣởng của nhiệt độ đối 
với độ tin cậy của mạng manet”, FAIR 2015. 
[2] Anil Choudhary, O. P. Roy and T. Tuithung, “Reliability Modeling of a Cluster Based Distributed Mobile Ad-hoc Network”, 
International Journal of Computing and Digital Systems, 2015 
[3] Changlei Liu, Guohong Cao, “Spatial-Temporal Coverage Optimization in Wireless Sensor Networks”, IEEE, 2011. 
[4] JasonCook, “Reliability of Mobile Ad-hoc Wireless Networks”, 2008. 
[5] L. Venkatesan and S. Shanmugavel, “Reliable Energy Efficient Fault Tolerant Clustering in Wireless Sensor Network”, Asian 
Journal of Scientific Research, Page No.: 33-44, 2014. 
[6] Tao Wang and William N. N. Hung, “Reliable Node Clustering for Mobile Ad Hoc Networks”, 2013. 
[7] Zeyu Sun, Heng Li, Heng Chen and Wei Wei, “Optimization Coverage of Wireless Sensor Networks Based on Energy 
Saving”, International Journal of Future Generation Communication and Networking, Vol.7, No.4 (2014). 
[8] Youssef Charfi, Naoki Wakamiya and Masayuki Murata, “Trade-off between Reliability and Energy Cost for Content-Rich 
Data Transmission in Wireless Sensor Networks”, IEEE, 2006. 
[9] Jietai Wang; Guangxue Yue, “Multipath Routing Protocol of Wireless Multimedia Sensor Networks Based on Mobile Agent”, 
Information Technology Journal;2013, Vol. 12 Issue 18, p3804. 
Lê Khánh Dƣơng, Lê Quang Minh, Nguyễn Anh Chuyên, Tô Hữu Nguyên 117 
A PROPOSED RELIABILITY ESTIMATION METHOD FOR MANET BASED 
ON CLUSTERING ALGORITHM AND NETWORK REDUNDANCY 
Le Khanh Duong, Le Quang Minh, Nguyen Anh Chuyen, To Huu Nguyen 
ABSTRACT— In mobile ad-hoc network, nodes can move from location to a new location, this movement makes network topology 
changes in realtime and greatly influenced to the quality of services of the network. The calculation of the reliability of the network 
encounters many difficulties because of the network unstructured. This paper proposes a method for calculating the reliability of the 
network-based clustering to reduce the complex of network structure in calculation and thereby applying the contingency plan to 
improve the reliability of mobile ad-hoc network. 
Keywords – MANET, Reliability, Clustering, Redundancy.