Nghiên cứu cải tiến, áp dụng cây tìm kiếm tam phân để lưu trữ và tìm kiếm vị từ
Nghiên cứu cải tiến, áp dụng cây tìm kiếm tam phân để
lưu trữ và tìm kiếm vị từ cho kỹ thuật chuyển tiếp thông
điệp trong định tuyến hướng dịch vụ
Nguyen Thanh Long
Informatic Center of Ha noi Telecommunications
75 Dinh Tien Hoang, Hoan Kiem, Ha Noi, Viet Nam

Nguyen Duc Thuy
Research Institute of Posts and Telecommunications
122 Hoang Quoc Viet, Nghia Tan, Cau Giay, Hanoi, Viet Nam

Pham Huy Hoang
Hanoi University of Science and Technology
1 Dai Co Viet Road, Hanoi, Viet Nam

__________________________________________________________________________________________
Tóm tắt
MANET là viết tắt của Mobile Ad Hoc Network bao gồm 1 tập các node mạng di động, cấu hình mạng
thay đổi rất nhanh. Mỗi node phải thực hiện như 1 bộ định tuyến để duy trì hoạt động của mạng. Không có node
trung tâm điều khiển hoạt động toàn bộ mạng. Không có một nền tảng có sẵn nào, các node mạng phải tự liên kết
với nhau, hình thành cấu trúc mạng tự động. Do vậy việc định tuyến trong MANET là một việc quan trọng.
Trong định tuyến hướng nội dung, dữ liệu được truyền từ node nguồn đến tập các node có yêu cầu không dựa
trên địa chỉ node nhận. Việc trao đổi dữ liệu có thể được thực hiện không trực tiếp giữa bên nhận và bên truyền.
Vì vậy việc trao đổi dữ liệu mềm dẻo và tin cậy hơn kiểu truyền dữ liệu truyền thống. Mô hình
Publish/Subscription (P/S) là kiểu tương tác không đồng bộ được thực hiện trong các hệ thống định tuyến dựa
trên nội dung [3].Định tuyến hướng dịch vụ được xây dựng trên cơ sở kế thừa từ mô hình định tuyến hướng nội
dung [3, 4], được kết hợp với 1 số kỹ thuật quan trọng như đa truyền phát (Multicast) để tăng tốc độ truyền, giảm
tải cho mạng, mã hoá dữ liệu đảm bảo an toàn. Kết hợp với đảm bảo chất lượng dịch vụ (QoS) như băng thông,
độ trễ để phục vụ cho các ứng dụng quan trọng như Multimedia, ứng dụng trực tuyến, ...
Để truyền dữ liệu hiệu quả và nhanhyêu cầu việc lưu trữ các địa chỉ theo nội dung một cách khoa học, giúp

node nhận được sẽ kiểm tra xem có các node nào có
yêu cầu sẽ gửi nội dung này cho các node đó.Mỗi
node mạng có thểđảm nhận cùng 1 lúc các vai trò:
cung cấp nội dung, phân phát nội dung, nhận nội
dung. Hiện tại có nhiều giao thức định tuyến đã
được áp dụng cho MANET như OLSR, CBR, DSR,
DSDV, AODV, ODMRP, … trong đó có cả định
tuyến theo nội dung.
2. Cấu trúc của các loại thông điệp
trong mạng SBR
Hình 2: Mô hình truyền thông điệp trong mạng định
tuyến hướng dịch vụ.
2.1.Giới thiệu các loại thông điệp[3,4,6]
1. Cặp thông điệp subscription/unsubscription: dùng để
đăng ký/ huỷ đăng ký yêu cầu tìm kiếm nội dung từ
1 node của mạng.
2. Thông điệp content: cung cấp nội dung của node lên
mạng.
3. Thông điệp quảng bá nội dung: quảng bá nội dung
node, hướng các yêu cầu từ các node đến các node
cung cấp nội dung phù hợp. Tránh làm tràn các yêu
cầu ra toàn mạng. Khi 1 node quảng bá nội dung của
nó sử dụng giao thức broadcast, nội dung này được
lưu trữ tại tất cả các node trong mạng. Khi 1 thông
điệp yêu cầu xuất hiện trong mạng, tại node nhận
được thông điệp sẽ kiểm tra thông điệp xem có phù
hợp với nội dung công bố của nó. Nếu đúng nội
dung phù hợp sẽ được gửi đến node có yêu cầu. Nếu
không, nó sẽ so sánh với các thông điệp quảng bá
nội dung được cache trên node. Rồi thông điệp yêu

hiện các tuyến từ node nguồn đến tập node đích để
hình thành cây multicast có đảm bảo các yêu cầu
chất lượng dịch vụ để truyền thông điệp nội dung
nhận được đến tập các node có yêu cầu phù hợp.Đối
với các ứng dụng có yêu cầu tốc độ truyền như
multimedia, online transaction, có thể sử dụng các
Nghiên cứu cải tiến, áp dụng cây tìm kiếm tam phân để lưu trữ và tìm kiếm vị từ
thuật toán được trình bày ở phần sau để xây dựng
cây multicast có đảm bảo băng thông truyền.
2.2. Thông điệp yêu cầu/ huỷ yêu cầu [3,4]:
Thông điệp yêu cầu/ hủy yêu cầu được phát ra từ
các lớp dịch vụ ứng dụng trên mạng để đăng ký/ huỷ
đăng ký các yêu cầu nội dung. Các thông điệp có
cấu trúc là: địa chỉ của subscriber và danh sách các
ràng buộc trên dịch vụ và nội dung yêu cầu. Trong
đó, mỗi ràng buộc là 1 bộ 3 thành phần, có dạng:
{key, operator, value}. Ví dụ nội dung của thông
điệp đăng ký: [service_class=”Network monitor”
Λ
alert-type=”instrusion”
Λ
severity>2] hoặc [service_class=”Network monitor”
Λ
class=”alert”
Λ
device-type=
“web-server”], 2 thông điệp yêu cầu thuộc lớp dịch
vụ Network monitor.
a) Cấu trúc thông điệp yêu cầu/ hủy yêu cầu
Hình 3:Cấu trúcthông điệp yêu cầu.

Thông điệp nội dung được truyền đi từ các máy
chủ cung cấp dịch vụ. Các thông điệp này sẽ được
truyền lên mạng, rồi sẽ được truyền đến các máy có
yêu cầu căn cứ vào subscription message nhận được
từ các máy đó.
a) Cấu trúc thông điệp nội dung
Hình 4 :Cấu trúcthông điệp nội dung.
Trong đó:
1)Source node address là địa chỉ node sinh ra thông
điệp.
2)Tiếp theo attribute
1
, attribute
2
, …, attribute
n
là các
thuộc tính của thông điệp. Thuộc tính đầu tiên
attribute
1
xác định dịch vụ của thông điệp, các
thuộc tính còn lại xác định nội dung của thông
điệp.
b) Các thành phần của thông điệp nội dung:
1) Thông điệp nội dung bao gồm địa chỉ node sinh ra
thông điệp và 1 tập các thuộc tính (property), mỗi
thuộc tính là 1 cặp (tên thuộc tính, giá trị) được
ngăn cách nhau bởi dấu “=”.
2) Tên thuộc tính là một chuỗi ký tự.
3) Giá trị có thể có kiểu chuỗi ký tự hoặc kiểu số.

nhận trả lời. Thông điệp này được truyền theo cây
khung tối thiểu (Minimum Spanning Tree viết tắt là
MST) bắt đầu từ router gửi (hình thành theo thuật
toán DIJSKTRA và PRIM) đến các router khác
trong mạng.
2) Khi router lá của cây MST nhận được thông điệp
sender request, nó sẽ trả lời bằng thông điệp update
reply (UR). Thông điệp gồm có 3 trường, 2 trường
đầu lấy từ sender request, trường thứ 3 lưu trữ
content based address routing table của nó. Thông
điệp UR được lan truyền trở lại router gửi theo giao
thức unicast.
3) Trên đường đi các router trung gian sẽ kết hợp
content based address routing tablecủa nó với của
thông điệp và đẩy tiếp về router gửi.
4) Khi router gửi nhận được nó cập nhật bảng định
tuyến của nó. Kết thúc quá trình thực hiện.
3. Các khái niệm và thuật ngữ
3.1. Khái niệm bảng chuyển tiếp theo dịch
vụ
a) Mỗi dịch vụ có 1 bảng chuyển tiếp riêng.
b) Bảng chuyển tiếp bao gồm các vị từ
(predicate) hay còn được gọi là content-based
address.
c) Bảng chuyển tiếp là liên kết 1-1 giữa
Predicate và định danh của các subscriber.
d) Predicate là tuyển của các bộ lọc nhận được
từ subscriber.
e) Thuật toán chuyển tiếp là giải thuật tìm
trong bảng chuyển tiếp các filter phù hợp với nội

theo.
Tìm kiếm các ràng buộc phù hợp:
Khi nhận được thông điệp nội dung từ mạng, hệ
thống sẽ duyệt qua các thuộc tính của thông điệp.
Với mỗi thuộc tính căn cứ vào giá trị của thuộc tính,
rồi tìm kiếm trong cây tìm kiếm tam phân với thuộc
tính có giá trị chuỗi. Nếu là thuộc tính có giá trị số:
áp dụng tìm kiếm nhị phân trên 1 danh sách.
4. Cách lưu trữ vị từ bằng cây tam
phân cho ràng buộc có giá trị chuỗi
4.1. Tổng quan cây tìm kiếm tam phân
1) Cây tìm kiếm tam phân là 1 cấu trúc dữ liệu
dạng cây ở đó các node con của 1 cây chuẩn được
sắp xếp như 1 cây tìm kiếm nhị phân. Việc tìm kiếm
1 chuỗi trong 1 cây tìm kiếm tam phân bao gồm 1
loạt các bước tìm kiếm nhị phân, mỗi bước cho việc
tìm kiếm 1 ký tự trong chuỗi. Ký tự hiện tại trong
chuỗi được so sánh với ký tự tại node hiện tại:
a) Nếu nhỏ hơn thì tìm kiếm
tiếp với node con bên trái.
b) Nếu lớn hơn thì tìm kiếm
tiếp với node con bên phải.
c) Nếu bằng nhau, thì tìm
kiếm tiếp với node con giữa và chuyển sang ký
tự tiếp theo trong chuỗi.
2) Không giống như cây tìm kiếm nhị phân, 1
cây tìm kiếm tam phân có thể cân bằng hoặc không
cân bằng, dựa trên thứ tự của các chuỗi được thêm
vào cây. Việc tìm kiếm 1 chuỗi độ dài m trong 1 cây
tìm kiếm tam phân cân bằng có n chuỗi phải sử dụng

g) Các phần tử lưu trữ toán tử của các ràng buộc
có cùng giá trị được lưu trữ trong 1 mảng động. Mỗi
phần tử của mảng động có 3 thành phần: op: lưu trữ
toán tử; start idx viết tắt của start index: lưu trữ vị trí