Định tuyến quảng bá trong mạng cảm biến không dây

 chí khoa học, Tập 50 - Số 1A/2021, tr. 14-20 
 2. Kiến thức liên quan 
 2.1. Phân loại giao thức quảng bá trong mạng cảm biến không dây 
 Đã có nhiều đánh giá khảo sát các loại định tuyến quảng bá nhằm mục đích chỉ ra 
các ưu nhược điểm của chúng như trong [5-6]. Từ đó xem xét các nút cảm biến tham gia 
vào quá trình chuyển tiếp như thế nào, kết quả ra quyết định chuyển tiếp của mỗi phương 
pháp có tự nhiên, ngẫu nhiên, hiệu quả hay không. Từ các khảo sát, giao thức quảng bá 
có thể được phân loại như sau. 
 a. Phương pháp tập trung và phân tán (Centralized and distributed algorithms): Các 
giao thức dựa vào phương pháp tính toán để tiến hành phân loại. Phương thức tập trung 
thường dựa trên toàn bộ thông tin của mạng để có được kết quả tốt nhất. Nhưng trong phần 
lớn các ứng dụng cảm biến không dây, sử dụng toàn bộ thông tin về mạng để tiến hành tính 
toán là rất khó và tốn kém chi phí, thời gian. Do đó, thông thường các giao thức sử dụng 
phương thức phân tán để tiết kiệm chi phí, giảm thời gian và năng lượng 
 b. Phương pháp cắt xén và không cắt xén (Based on tailoring and non - tailoring 
algorithms). Với phương pháp cắt xén, các nút cảm biến được tạo thành các cây bao trùm 
giúp giảm thiểu thời gian chuyển tiếp gói tin giữa các nút do chỉ sử dụng các nút trong 
cây bao trùm để chuyển tiếp gói tin. Do tập nút bao phủ có thể có được bằng nhiều cách 
thức, nên từ đó phương pháp này dễ dàng được thực hiện và có thể cùng với các phương 
pháp khác như tập thống trị để kết hợp nhằm tạo ra hiệu quả tốt nhất. 
 c. Phương pháp chỉ định (gán) nút hàng xóm và tự quyết định: Đây là phương 
pháp dựa vào tập nút hàng xóm để quyết định có tham gia vào quá trình chuyển tiếp hay 
không. Hoặc do tự nút quyết định có tham gia hay không. Đối với phương pháp tiếp cận 
này, các nút trước khi thực hiện chuyển tiếp phải sửa đổi thông tin của tiêu đề gói tin. 
Phương pháp này có thể giảm thiểu thông tin chuyển tiếp trong mạng, thích hợp với 
mạng có cấu trúc thay đổi thường xuyên. 
 d. Phương pháp dựa vào xác xuất và phương pháp xác định: Đây là phương pháp 
dựa vào tính toán quyết định có thay đổi so với dự đoán ban đầu hay không? Trong 
phương pháp xác xuất, quyết định chuyển tiếp không được đảm bảo. 100% các nút đều 
nhận được gói dữ liệu, với hiệu suất tương đối kém. Tuy nhiên phương pháp này là tương 
đối đơn giản, thông thường yêu cầu rất nhỏ các thông tin ra quyết định, cụ thể đối với 
tính mở rộng và mật độ nút dày của mạng thìphương pháp quyết định là rất tốt. 
 e. Phương pháp điều tiết công suất và không điều tiết công suất: Trong phương 
pháp điều tiết công suất, các nút có thể dựa vào thông tin công suất tương quan, công 
suất nhỏ nhất có thể để chuyển tiếp, tiết kiểm năng lượng tiêu thụ. Tuy nhiên với phương 
pháp này, lợi dụng kỷ thuật tầng mạng nên cần thiết phải có kiến thức và hiểu biết sau về 
tầng mạng. 
 g. Phương pháp dựa trên tập các nút thống trị và không dựa trên các nút thống trị: 
Phương pháp thông qua xây dựng một tập các nút thống trị (CDS) và các thông tin bảo 
trì liên quan. Tại các mạng có sự thay đổi (dynamic) lớn thì chi phí cho việc bảo trì cao, 
đối với mạng tĩnh có thể có được giao thức tương đối ổn định. Phương pháp dựa trên tập 
thống trị thường thích hợp với mạng có công suất các nút không thể điều tiết. Ngoài ra có 
thể sử dụng phương pháp kết cấu và không kết cấu đồ thị của mạng để tăng thêm hiệu 
quả cho tập việc xây dựng thống trị và hiệu quả của định tuyến. 
 15 
 Nguyễn Quốc Dũng, Nguyễn Thị Việt / Định tuyến quảng bá trong mạng cảm biến không dây 
 h. Phương pháp không sử dụng thông tin tín hiệu (beacon) và có sử dụng thông 
tin beacon: Phương pháp không có beacon không yêu cầu trao đổi thông tin beacon, 
thông tin overhead nhỏ, thuộc về giao thức quảng bá không trạng thái, thích hợp cho các 
mạng có sự thay đổi lớn, hơn nữa, có khả năng mở rộng với các mạng có quy mô lớn. 
Nhưng đối với các loại phương pháp này thực hiện rất là phức tạp, khó khăn. 
 i. Phương pháp dựa trên phạm vi bao phủ của truyền tải và không thuộc phạm vi 
bao phủ truyền tải: Trong giao thức dựa vào phạm vi bao phủ truyền tải, các nút lợi 
dụng phạm vi bao phủ của các nút tham gia chuyển tiếp gói tin trước đó mà không dựa 
vào cấu trúc mạng để quyết định có tham gia vào chuyển tiếp gói tin hay không? Mặc 
dù phương pháp này sử dụng thông tin vị trí địa lý của các nút, nhưng rõ ràng đã giảm 
thiểu đi rất nhiều thông tin beacon trao đổi của các nút hoặc là hoàn toàn không cần 
đến thông tin beacon. 
 j. Phương pháp dựa vào định hướng antena và toàn hướng antena: Trong mạng có 
mật độ các nút thấp lợi dụng tính định hướng truyền tải có thể tăng hiệu quả sử dụng 
năng lượng, nhưng điều này cần các nút có hỗ trợ các antena định hướng. Ngược lại, đối 
với các mạng có mật độ nút lớn thì sử dụng antena toàn hướng có thể tăng hiệu quả 
quảng bá không dây. 
 2.2. Một số giao thức định tuyến quảng bá phổ biến 
 Trong phần này, chúng tôi sẽ trình bày một số giao thức quảng bá định tuyến phổ 
biến được áp dụng cho các mạng cảm biến không dây tĩnh bao gồm: giao thức đa kênh 
EMBA, giao thức hiệu quả phủ sóng CEB và giao thức bảo toàn năng lượng EENWB. 
 a. Giao thức EMBA 
 Trong [2], các tác giả đề xuất một giao thức quảng bá định tuyến truyền phát đa 
kênh hiệu quả (An Efficient Multihop Broadcast Protocol for Asynchronous Duty-Cycled 
wireless Sensor Networks - EMBA). EMBA tăng hiệu quả quảng bá đa điểm cho các nút 
cảm biến thông qua sử dụng các thông tin va chạm và hạn chế phát lại gói tin dự phòng. 
EMBA cho thấy hiệu quả sử dụng năng lượng cao, giảm chi phí gói tin trong cả hai 
trường hợp mạng có mật độ thưa và dày đặc. EMBA được đề xuất dùng cho các mạng 
cảm biến không dây không đồng bộ theo chu kỳ (asynchronization duty-cycled). EBMA 
dựa vào cách tiếp cận quảng bá nhiều điểm (multihop broadcast protocol) kết hợp hai kỷ 
thuật “định hướng gửi tin (Forwarder’s guidance)” và “lắng nghe các thông tin quảng bá 
(Overhearing broadcast)” dẫn đến giảm số lượng gói tin phát tán quảng bá, giảm va chạm 
gói tin, cũng như tối ưu hóa năng lượng. Tuy nhiên, EMBA tăng gói tin overhead để điều 
khiển quá trình định hướng và lắng nghe gói tin trong mạng. 
 Mô hình mạng EMBA bao gồm một tập nút phân bổ ngẫu nhiên, trong mạng có 
thể tạo thành các vùng đa giác (n-đỉnh) hoặc tam giác (3-đỉnh), tần suất xuất hiện của đa 
giác phụ thuộc vào mật độ của mạng. Các nút trong mạng là cố định, không có khả năng 
di chuyển. Mỗi một nút sẽ duy trì một bảng hàng xóm cấp 1 và một bảng hàng xóm cấp 2 
trong đó gồm thông tin chất lượng liên kết tới nó. Các nút trong mạng sẽ được phân chia 
thành các nhóm như trong Bảng 1. 
 16 
Trường Đại học Vinh Tạp chí khoa học, Tập 50 - Số 1A/2021, tr. 14-20 
 B ng 1: Tập hợp các nút của EMBA 
 Tập Phần tử Bắt đầu 
 N(s) Tập các nút hàng xóm của nút S 
 i
 N cv(s) Tập các nút hàng xóm đã gửi gói tin bởi S 
 i
 N ucv(s) Tập các nút hàng xóm phát hiện bởi nút S N(s) 
 i i
 N oblg(s) Tập các nút bắt buộc phải gửi bởi nút S N ucv(s) 
 i
 N dg(s) Tập các nút hàng xóm được ủy quền gửi thay nút S 
 b. Giao thức CEB 
 Trong tài liệu [7], các tác giả đã đề xuất một giao thức quảng bá dựa trên tính 
hiệu quả phủ sóng (Coverage Efficiency-based Broadcast - CEB). Một nút sẽ dựa vào 
thông tin các nút trong bảng hàng xóm để xác định vai trò của nó là bắt buộc hay là được 
ủy quyền để chuyển tiếp gói tin (obligated or delegator). Theo đó, dựa theo thông tin các 
gói nhận được, một nút sẽ chia các nút hàng xóm thành ba trạng thái: tập các nút gửi 
(SS), tập hợp nút được bao phủ đơn (SCS), và tập hợp nút được bao phủ nhiều (MCS). 
Trạng thái của các nút trong ba tập hợp này sẽ được sử dụng để xác định nút được 
chuyển tiếp gói tin tiếp theo. 
 So với giao thức quảng bá EMBA, trong CEB, thuật toán chuyển tiếp gói tin tại 
một nút I sẽ dựa trên tỷ lệ giữa số nút trong SCS (| SCSi |) trên tổng số nút hàng xóm (| 
Neighbori |) giúp CEB sẽ cải thiện chất lượng phát sóng. Kết quả là CEB đã giảm đáng 
kể số lượng gói tin quảng bá. Tuy nhiên, trong EMBA và CEB, các nút chỉ dựa trên chất 
lượng của các liên kết để chuyển tiếp gói tin. Khi đó, một gói tin có thể phải chờ cho đến 
lượt được chuyển tiếp, điều này có thể làm tăng thời gian chuyển tiếp, hơn nữa làm cho 
nút gửi phải duy trì hoạt động liên tục để chuyển tiếp gói tin mà không đi vào trạng thái 
nghỉ để tiết kiệm năng lượng. 
 c. Giao thức EENWB 
 Để cải thiện hiệu quả quảng báo định tuyến, trong [8], các tác giả đã đề xuất một 
giao thức quảng bá toàn mạng tiết kiệm năng lượng (energy-efficient network-wide 
broadcast - EENWB). Giao thức EENWB dựa trên chất lượng liên kết và sự hợp tác tích 
cực giữa các nút gửi lân cận. Một nút gửi trong EENWB có thể đi vào trạng thái nghỉ 
sớm hơn để tiết kiệm năng lượng. Trong EENWB, khi nút gửi A đã ủy quyền phát sóng 
cho những nút gửi liền kề, thì nút gửi A có thể đi ngủ sớm hơn nếu các nút gửi liền kề có 
chất lượng liên kết tốt hơn chính nó liên kết đến các nút lân cận. Tuy nhiên, trong trường 
hợp gói tin được ủy quyền gửi đến muộn hoặc nút ủy quyền có chất lượng liên kết kém 
thì giao thức EENWB không tiết kiệm năng lượng và tăng độ trễ phát sóng. 
 3. Đánh giá mô phỏng 
 Trong phần này chúng tôi thực hiện đánh giá và so sánh hiệu năng của các giao 
thức EMBA, CEB và EENWB như đã giới thiệu ở mục 2.2. Thông qua các thuật toán 
của từng giao thức quảng bá, chúng tôi đã thực hiện cài đặt và đánh giá thông qua công 
cụ mô phỏng NS2, đây là công cụ hỗ trợ mô phỏng và đánh giá hiệu năng mạng rất phổ 
biến hiện nay. Mô phỏng đánh giá của chúng tôi được thực hiệnvới các kịch bản mạng 
cómật độ các nút cảm biến khác nhau gồm 50, 100, 150, 200 nút nhằm đánh giá hiệu quả 
của các giao thức quảng bá trong nhiều trường hợp khác nhau. Các nút được triển khai 
 17 
 Nguyễn Quốc Dũng, Nguyễn Thị Việt / Định tuyến quảng bá trong mạng cảm biến không dây 
ngẫu nhiên trong diện tích mạng 400 x 200 m2, và thời gian mô phỏng cho mỗi kịch bản 
là 400s. Một số thông số khác của mạng cảm biến không dây như trong phần mô phỏng 
đánh giá ở tài liệu [9]. 
 3.1. Số lượng gói tin phân phát 
 Trong quảng bá, số lượng gói tin phân phát là số liệu quan trọng để đánh giá chất 
lượng của giao thức đó. Gói tin phân phát càng thấp thì hiệu quả quảng bá của giao thức 
càng cao. Nhưng trong Hình 1, khi số nút trong các kịch bản tăng lên thì tổng số gói tin 
phân phát cũng tăng theo. Đặc biệt với các giao thức CEB, tổng số gói tin có xu hướng 
tăng lên nhanh khi tổng số nút cảm biến của mạng tăng lên. Trong giao thức EENWB, 
các gói tin được uỷ nhiệm phân phát, do đó tổng số gói đã giảm đi đáng kể so với hai 
giao thức còn lại dẫn đến giảm chi phí băng thông, tránh xung đột gói tin. 
 Hình 1: Tổng số gói tin phân phát cho các giao thức quảng bá 
 3.2. Năng lượng trung bình còn lại 
 Đánh giá năng lượng còn lại trong mạng thể hiện sự tối ưu, khả thi trong triển khai 
mạng cảm biến không dây trong thực tế. Các cảm trong môi trường triển khai tồn tại càng 
lâu càng tốt. Chúng tôi đã đánh giá tổng năng lượng còn lại của các giao thức sau khi kết 
thúc mô phỏng. Như trong Hình 2, năng lượng còn lại của các giao thức không chênh lệch 
nhau nhiều. Trong đó EENWB có năng lượng trung bình còn lại cao hơn các giao thức 
khác. Điều này có được là do các nút đã đi vào trạng thái ngủ để bảo toàn năng lượng. 
 Hình 2: Năng lượng trung bình còn lại của các giao thức 
 18 
Trường Đại học Vinh Tạp chí khoa học, Tập 50 - Số 1A/2021, tr. 14-20 
 4. Kết luận 
 Nghiên cứu định tuyến gói tin là một trong những nội dung rất được quan tâm 
trong mạng cảm biến không dây. Trong bài báo này, chúng tôi đã tổng kết về các loại 
giao thức quảng bá trong mạng cảm biến không dây từ đó đánh giá và phân loại một số 
loại giao thức quảng bá. Thông qua các đánh giá về một số giao thức định tuyến quảng 
bá như EMBA, CEB, EENWB, bài báo sẽ là cơ sở lý thuyết cho các nghiên cứu, đề xuất 
cải tiến giúp tăng hiệu quả cho mạng cảm biến không dây và cải tiến giao thức định 
tuyến quảng bá dựa vào tối ưu cấu trúc liên kết của các nút cảm biến. 
 TÀI LIỆU THAM KHẢO 
[1] Qing Liu, Anfeng Liu, “On the hybrid using of unicast-broadcast in wireless sensor 
 networks,” Computers and Electrical Engineering 71: 714-732, 2018. 
[2] Ingook Jang, Suho Yang, Hyunsoo Yoon, “EMBA: An Efficient Multihop Broadcast 
 Protocol for Asynchronous Duty-Cycled wireless Sensor Networks,” Ieee 
 Transactions On Wireless Comm. 12.4: 1640-1650, 2013. 
[3] Zhuangbin Chen, Anfeng Liu, Zhetao Li, Young-June Choi, Hiroo Sekiya, and Jie Li, 
 “Energy-Efficient Broadcasting Scheme for Smart Industrial Wireless Sensor 
 Network,” Mobile Information Systems, 17, 2017. 
[4] I. F. Akyildiz, W. Su, Y. Sankarasubramaniam, and E. Cayirci, “Wireless sensor 
 networks: A survey,” Comput. Netw., 38.4, 393-422, 2002. 
[5] Xiaohong Shen, “Broadcast Protocols for Wireless Sensor Networks,” Smart Wireless 
 Sensor Networks, 85-99, 2010. 
[6] Tang Yong, Xiang Yu, Zhang Jun and Wang Wenyong, “A survey on broadcast in 
 wireless sensor networks,” The 2nd International Conference on Information 
 Science and Engineering, 4324-4331, 2010. 
[7] Xinming Zhang, Fan Yan, Chao Li, and Qing Ding, “Coverage Efficiency-Based 
 Broadcast Protocol for Asynchronous Wireless Sensor Networks,” Ieee Wireless 
 Communications Letters 5.1: 76-79, 2016. 
[8] X. Wang, X. Wu, X. Zhang, and Y. Liang, “An Energy-Efficient Network-Wide 
 Broadcast Protocol for Asynchronous Wireless Sensor Networks,” IEEE Wireless 
 Communications Letters 7.6: 918-921, 2018. 
[9] D. N. Quoc, L. Bi, Y. Wu, S. He, L. Li, and D. Guo, “Energy Efficiency 
 Clustering based on Gaussian Network for Wireless Sensor Network,” 
 IET Communications 13. 6:741-747, 2019. 
 19 
 Nguyễn Quốc Dũng, Nguyễn Thị Việt / Định tuyến quảng bá trong mạng cảm biến không dây 
 SUMMARY 
 BROADCAST ROUTING 
 IN WIRELESS SENSOR NETWORK 
 Nguyen Quoc Dung (1) (2), Nguyen Thi Viet (1) 
 1 Faculty of Engineering - Technology, Ha Tinh University, Vietnam 
 2 Institute of Electronics - Technology, Xiamen University, China 
 Received on 31/12/2020, accepted for publication on 29/3/2021 
 The wireless sensor networks are interested in research and widely applied in 
some fields such as industry, agriculture, medical, military, and transportation. 
Broadcasting is an important application of wireless sensor networks. This paper has 
analyzed, classified and evaluated some broadcast approaches in wireless sensor 
networks. Based on the analysis and survey of broadcast routing protocols, the paper 
has built a simulation scenario in the NS2 network simulation to evaluate and compare 
the performance of some protocols such as EMBA, CEB and EENWB. These results 
are the theoretical basis for research and proposal to improve the efficiency of wireless 
sensor networks. 
 Keywords: Wireless sensor network; broadcast routing; throughput. 
 20