ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ Phạm Đình Hậu XÂY DỰNG ỨNG DỤNG TÌM KIẾM THÔNG TIN
THEO VỊ TRÍ TRÊN MẠNG NGANG HÀNG CÓ
CẤU TRÚC

KHOÁ LUẬN TỐT NGHIỆP ĐẠI HỌC HỆ CHÍNH QUY

Ngành: Công nghệ thông tin Cán bộ hướng dẫn: TS.Nguyễn Hoài Sơn

HÀ NỘI - 2009

LỜI CẢM ƠN
Để hoàn thành khóa luận này, trước hết em xin bày tỏ lòng biết ơn sâu sắc tới
thầy TS. Nguyễn Hoài Sơn. Thầy đã tận tình hướng dẫn, giúp đỡ em trong suốt quá
trình làm khóa luận. Đồng thời em xin được cảm ơn các thầy giáo, cô giáo trong
Trường Đại Học Công Nghệ - Đại Học Quốc Gia Hà Nội đã truyền đạt cho em
nhiều kiến thức bổ ích trong suốt thời gian h
ọc tập tại trường.
Cuối cùng, em xin cảm ơn tất cả bạn bè, gia đình và người thân đã giúp đỡ, động
viên em rất nhiều để em có thể hoàn thành tốt khoá luận. Hà Nội, ngày 25 tháng 5 năm 2009

được các yêu cầu của dịch vụ dựa vào vị trí là cung cấp dịch vụ thời gian thực và có
thể dễ dàng mở rộng hệ thống.
MỤC LỤC
LỜI MỞ ĐẦU 1
CHƯƠNG 1. MÔ HÌNH DỊCH VỤ DỰA VÀO VỊ TRÍ 3
1.2. Tổng quan về dịch vụ dựa vào vị trí 3
1.3. Các thành phần của dịch vụ dựa vào vị trí 4
1.3.1. Thiết bị di động 5
1.3.2. Mạng kết nối 6
1.3.3. Thành phần định vị 8
1.3.4. Nhà cung cấp ứng dụng và dịch vụ 9
1.4. Cách thức hoạt động của dịch vụ dựa vào vị trí 10
1.5. Tìm kiếm thông tin dựa vào vị trí 11
1.6. Tổng kết 12
CHƯƠNG 2. PHƯƠNG PHÁP TÌM KIẾM THÔNG TIN TRÊN MẠNG NGANG HÀNG
CÓ CẤU TRÚC 13
2.1. Tổng quan về mạng ngang hàng 13
2.1.1. Khái niệm mạng ngang hàng 13
2.1.2. Ưu điểm và nhược điểm của mạng ngang hàng 14
2.1.3. Phân loại mạng ngang hàng 15
2.2. Mạng ngang hàng có cấu trúc 16
2.1.1. Tổng quan về mạng ngang hàng có cấu trúc 16
2.2.2. Mạng ngang hàng có cấu trúc CHORD 18
2.3. Tìm kiếm thông tin trên mạng ngang hàng có cấu trúc 22
2.3.1. Tìm kiếm chính xác 22
2.3.2. Tìm kiếm theo thuộc tính – giá trị 22
2.3.3. Tìm kiếm theo khoảng 23

Hình 8. Cách thức hoạt động của dịch vụ dựa vào vị trí 10
Hình 9: Mô hình mạng ngang hàng 13
Hình 10. Hệ thống mạng ngang hàng lai ghép 15
Hình 11. Mạng ngang hàng có cấu trúc Chord dạng vòng tròn 17
Hình 12. Mô hình mạng Chord 19
Hình 13: Định nghĩa các trường trong bảng định tuyến của Chord 19
Hình 14. Minh hoạ quy tắc lưu khoá trong mạng Chord 20
Hình 15. Minh hoạ chia bề mặt trái đất thành các ô 28
Hình 16. Minh hoạ một ô của bề mặt trái đất được chia ra 28
Hình 17: Minh hoạ tìm kiếm thông tin trong một vùng 30
Hình 18: Minh hoạ thông tin vị trí của một ô trên bề mặt trái đất 31
Hình 20. Cấu trúc hệ thống dịch vụ tìm kiếm thông tin dựa vào vị trí 33
Hình 21: Minh hoạ việc tạo truy vấn theo ngữ cảnh 34
Hình 22: Yêu cầu địa chỉ IP và cổng của các máy trong mạng ngang hàng 34
Hình 23: Yêu cầu tìm kiếm của thiết bị di động gửi lên mạng ngang hàng 35
Hình 24: Minh hoạ mạng ngang hàng trả kết quả cho thiết bị di động 36
Hình 25: Minh hoạ giao diện hiển thị kết quả tìm kiếm thông tin 38
Hình 27: Giao diện hiển thị kết quả trên bản đồ 39
Hình 28: Mô hình thí nghiệm 39
Hình 29: Kết quả thí nghiệm 40
Hình 30: Đồ thị kết quả thử nghiệm 41 1

LỜI MỞ ĐẦU
Ngày này, số lượng các thiết bị di động cầm tay tăng nhanh, sức mạnh xử lý và
bộ nhớ của thiết bị đã có thể đáp ứng được yêu cầu của nhiều dịch vụ. Trong đó dịch
vụ dựa vào vị trí là một dịch vụ phổ biến và đang phát triển hiện nay. Dịch vụ này
được ứng dụng trong nhiều lĩnh vự

là có thể quản lý, lưu trữ và tìm kiếm trên quy mô lớn, có tính phân tán và có thể
dễ
dàng mở rộng. Vì vậy khoá luận đã đi sâu vào nghiên cứu và xây dựng hệ thống tìm
kiếm thông tin theo vị trí dựa trên mạng ngang hàng có cấu trúc . Để đánh giá hiệu quả
của hệ thống đã xây dựng thì hệ thống đã được thử nghiệm trong môi trường được giới

2

hạn về băng thông và độ trễ giống với môi trường Internet và mạng điện thoại hiện nay
và kết quả thử nghiệm là khá khả quan.
Khoá luận được chia làm 5 chương:
- Chương 1: Chương này sẽ giới thiệu về cấu trúc của hệ thống dịch vụ dựa vào
vị trí hiện đang được sử dụng và các yêu cầu của dịch vụ dựa vào vị trí.
- Chương 2: Trong chươ
ng này sẽ giới thiệu tổng quan về mạng ngang hàng, ưu
nhược điểm của mạng ngang hàng và các phương pháp tìm kiếm đang được sử dụng
trong mạng ngang hàng có cấu trúc.
- Chương 3: Chương này sẽ trình bày về ý tưởng, yêu cầu và cách thức xây dựng
dịch vụ tìm kiếm thông tin theo vị trí dựa trên mạng ngang hàng có cấu trúc.
- Chương 4: Trong chương này chúng ta sẽ trình bày về mô hình thực nghiệm để
đánh giá hiệu quả của dịch vụ
tìm kiếm thông tin theo vị trí đã xây dựng và đưa ra các
nhận xét đánh giá kết quả thử nghiệm.
- Chương 5: Kết luận và hướng phát triển tiếp theo của khoá luận.

3

CHƯƠNG 1. MÔ HÌNH DỊCH VỤ DỰA VÀO VỊ TRÍ
Ngày nay, với sự tiến bộ của khoa học kỹ thuật, đặc biệt là sự phát triển nhanh
chóng của công nghệ phần cứng đã có thể tạo ra các thiết bị nhỏ gọn, có khả năng lưu

một vị trí mà người dùng mong muốn.
+ Tìm kiếm: Ứng dụng này có thể là cung cấp các thông tin về các dịch vụ gần
nhất (có thể là nhà hàng gần nhất, tr
ạm ATM gần nhất), các thông tin về giao thông
như tình trạng tắc nghẽn giao thông tại điểm nào đó.

4

+ Xác định một người hay vật: Dùng để xác định một vật hay người nào đó ở vị
trí hiện tại.
+ Kiểm tra sự kiện: Dùng để kiểm tra xem có sự kiện nào xảy ra ở vị trí này
không.
+ Dịch vụ khẩn cấp: Khi có các tình trạng khẩn cấp như hoả hoạn, lũ lụt, trộm
cướp thì có thể sử dụng dịch vụ này để thông báo cho cảnh sát hoặc cho lính cứu hoả
.
+ Dịch vụ theo dõi: Dịch vụ này có thể là theo dõi giao thông để thông báo cho
các các xe cứu thương hoặc cung cấp cho người dùng tránh các điểm tắc nghẽn.
1.3. Các thành phần của dịch vụ dựa vào vị trí
Dịch vụ dựa vào vị trí gồm có bốn thành phần như hình 1 [3]:
- Thiết bị di động
- Mạng kết nối
- Thành phần định vị
-Nhà cung cấp ứng dụng và dịch vụ

Hình 1. Cấu trúc hệ thống dịch vụ dựa vào vị trí

5

1.3.1. Thiết bị di động
Là các thiết bị Mobile Phone, Smart Phone, Laptop, PDA mà người dùng có

+ Mạng diện rộng không dây (WWAN: Wireless Wide Area Networks) thường
từ 100 m đến 35 km và yêu cầu người dùng phải đăng ký để được sử dụng. Mạng này
bao gồm GSM (Global System for Mobile, GPRS (General Packet Radio Service) và
UMTS (Universal Mobile Telecommunication System). GMM và GPRS có thể truyền
dữ li
ệu tối đa là 14 kbps và 115 kbps ngược lại UMTS có thể truyền tới 2 Mbps.

Hình 3. Mạng diện rộng không dây

7

+ Mạng cục bộ không dây (WLAN: Wireless Local Area Network): khoảng
cách từ 10 đến 150 m. Thiết bị di động có thể kết nối thông qua các điểm truy cập.

Hình 4. Mạng cục bộ không dây
+ Mạng cá nhân không dây (WPAN: Wireless Personal Area Networks): được
dùng cho các kết nối trong một khoảng ngắn xung quanh 10 m và hệ thống thường
không yêu cầu đăng ký sử dụng. Thông thường bao gồm Bluetooth và các thiết bị
Infrared (IrDA), dữ liệu truyền qua công nghệ Bluetooth có thể là 1 Mbps trong
khoảng cách 10 m và trong trường hợp IrDA (Inrared) nó có thể là 16 Mbps trong
khoảng 1.5 m.

Hình 5. Mạng cá nhân không dây

8

1.3.3. Thành phần định vị
Là thành phần dùng để xác định vị trí hiện tại của người dùng. Hiện nay có hai
phương pháp chính để xác định vị trí người dùng là dựa vào tín hiệu vệ tinh và dựa
vào các trạm sóng đài.

của người dùng, dịch vụ này thường được chia thành hai loại:
- Dịch vụ chức năng: Các dịch vụ cung cấp chức năng hỗ trợ người dùng 113,
115 (gọi dịch vụ
cấp cứu khẩn cấp chỉ thông qua một nút bấm).
- Dịch vụ thông tin: Cung cấp thông tin như “tìm quán ăn gần nhất”.
+ Dịch vụ đẩy đi (Push Services): Cung cấp thông tin dù người có có yêu cầu
hay không yêu cầu trực tiếp. Dịch vụ hoạt động tự động và làm việc khi xảy ra một sự
kiện được chỉ định như dịch vụ dự báo thời tiết, tin nhắn quảng cáo khi người dùng
đi
vào một khu vực nào đó.

10

1.4. Cách thức hoạt động của dịch vụ dựa vào vị trí
Hệ thống hoạt động dựa trên các thành phần như hình vẽ 8 [3]: Các thiết bị,
mạng kết nối, công nghệ xác định vị trí, máy chủ cung cấp dịch vụ và dữ liệu.

Hình 8. Cách thức hoạt động của dịch vụ dựa vào vị trí
Hoạt động của hệ thống sẽ như sau:
Bước 1: Đầu tiên các thiết bị di động cầm tay sẽ xác định vị trí của mình dựa vào
tín hiệu vệ tinh của hệ thống định vị toàn cầu, các cột sóng di động hoặc dựa vào các
điểm truy cập không dây.
Bước 2: Sau khi đã có được thông tin về vị
trí hiện tại thì thiết bị di động sẽ gửi
thông tin về vị trí của mình và thông tin cần tìm kiếm (như cửa hàng, khách sạn, trạm
ATM gần nhất) đến máy chủ cung cấp dịch vụ qua mạng kết nối.
Bước 3: Các máy chủ dịch vụ sẽ đọc yêu cầu của thiết bị di động, xử lý yêu cầu
và gửi kết quả cho thiết bị di động.
Bước 4:
Thiết bị di động sẽ hiển thị kết quả cho người dùng, kết quả có thể được

Yêu cầu của hệ thống dịch vụ tìm kiếm thông tin theo vị trí là hệ thống có thể lưu
trữ, xử lý, tìm kiếm dữ liệu trên quy mô lớn và có khả n
ăng mở rộng cao vì vậy việc
triển khai dịch vụ này trên mô hình khách - chủ là không phù hợp. Mạng ngang hàng
có cấu trúc là một giải pháp tốt để triển khai dịch vụ tìm kiếm thông tin theo vị trí vì
bản chất của mạng ngang hàng là quản lý, lưu trữ, xử lý thông tin phân tán và mạng
ngang hàng có cấu trúc có ưu điểm là có thể thể tìm kiếm thông tin nhanh, tìm kiếm
trên quy mô lớn và hệ thống có tính mở rộng cao.

12

1.6. Tổng kết
Chương này đã giới thiệu tổng quan về dịch vụ dựa vào vị trí, cấu trúc của dịch
vụ dựa vào vị trí, hoạt động của dịch vụ dựa vào vị trí cũng như các yêu cầu hệ thống
của dịch vụ này.
Qua các yêu cầu của dịch vụ này ta có thể thấy việc triển khai dịch vụ dựa vào vị
trí trên mạng ngang hàng là hoàn toàn khả thi vì khi triể
n khai dịch vụ này trên mạng
ngang hàng thì hệ thống sẽ có thể tận dụng được khả năng lưu trữ, xử lý thông tin của
các máy tham gia vào mạng chính vì vậy làm tăng khả năng xử lý tổng thể của hệ
thống. Khả năng xử lý tổng thể của hệ thống tăng sẽ làm cho thời gian đáp ứng của
dịch vụ nhanh, đáp ứng được dịch vụ th
ời gian thực và ưu điểm của mạng ngang hàng
là khả năng mở rộng dễ cao chính vì vậy hệ thống triển khai trên mạng ngang hàng sẽ
có được ưu điểm là khả năng mở rộng hệ thống dễ dàng.

13

CHƯƠNG 2. PHƯƠNG PHÁP TÌM KIẾM THÔNG TIN TRÊN MẠNG
NGANG HÀNG CÓ CẤU TRÚC

ới tính phi tập trung của Internet, bởi
bản chất của tài nguyên là phân tán, các thông tin lưu trữ không chỉ trên các máy chủ
mà ở cả các máy khách.
Xét về khía cạnh sức mạnh xử lý, mạng mạng ngang hàng có khả năng xử lý cao
hơn cả những máy chủ lớn nhất hiện nay do đó sử dụng mạng mạng ngang hàng có thể
cải thiện đáng kể hiệu quả của các phương pháp phân tích, xử lý dữ liệu và giải các bài
toán phức tạp (đây đều là những vấn đề vượt ra ngoài tầm xử lý của những máy chủ
tập trung khi số lượng truy vấn, tính toán tăng lên đến hàng trăm triệu mỗi ngày). Sở dĩ
như vậy là vì mạng ngang hàng đã tận dụng khả năng xử lý, khả năng lưu trữ còn thừa
của các máy tính tham gia mạng với những thuật toán phân tán hợp lý. Công nghệ này
đã chia việc xử lý lớ
n ra thành những việc xử lý nhỏ có thể phân tán giữa các máy tính
trong một mạng. Mỗi máy tính sẽ xử lý một phần dữ liệu và trả về kết quả xử lý cho
máy tính trung tâm, máy tính trung tâm sẽ ghép nối các kết quả này lại với nhau. Bằng
cách đó, ta có thể giải quyết được những bài toán phức tạp mà không cần phải nâng
cấp khả năng xử lý của hệ thống hiện tại.
Bên cạnh đ
ó, việc phân tán trách nhiệm cung cấp dịch vụ đến tất cả các nút trên
mạng sẽ giúp loại bỏ vấn đề ngừng trệ dịch vụ do nơi cung cấp duy nhất gặp sự cố.
Mạng ngang hàng cũng tận dụng được băng thông trên toàn bộ mạng vì việc tăng
số giao tiếp giữa các thiết bị mạng qua các đường truyền khác nhau sẽ làm giảm khả
năng tắc nghẽ
n mạng. Ngoài ra, khi càng nhiều máy tính tham gia vào mạng ngang
hàng thì tổng sức mạnh xử lý, khả năng lưu trữ và băng thông lại tăng theo điều đó cho
thấy khả năng mở rộng của mạng mạng ngang hàng.
Tuy nhiên, mạng ngang hàng cũng có nhiều nhược điểm. Với mô hình mạng
ngang hàng thuần túy, tức là mô hình mà ở đó mọi máy đều có vai trò như nhau và
không tuân theo bất cứ một quy luật định tuyến hay kết nố
i nào thì mạng mạng ngang
hàng cũng bộc lộ khá nhiều nhược điểm:

cấu trúc và mạng ngang hàng có cấu trúc.
Mạng ngang hàng không cấu trúc: Trong mạng ngang hàng không cấu trúc thì
các liên kết giữa các nút trong mạng được thiết lập ng
ẫu nhiên không theo quy luật.
Những mạng như thế này dễ dàng được xây dựng vì một máy mới khi muốn tham gia
mạng có thể lấy các liên kết có sẵn của một máy khác đang ở trong mạng và sau đó
dần dần tự bản thân nó sẽ thêm vào các liên kết mới cho riêng mình. Khi một máy
muốn tìm một dữ liệu trong mạng ngang hàng không cấu trúc, yêu cầu tìm kiếm sẽ
được truyền trên cả mạng để tìm ra càng nhiều máy chia sẻ càng tốt. Đạ
i diện cho mô
hình mạng này là mạng ngang hàng Gnutella.
2.2. Mạng ngang hàng có cấu trúc
2.1.1. Tổng quan về mạng ngang hàng có cấu trúc
Nhược điểm của mạng ngang hàng không có cấu trúc là không thể đảm bảo chắc
chắn sẽ tìm thấy một thông tin có tồn tại trên mạng ngang hàng do mạng này sử dụng
cơ chế tìm kiếm phát tràn tức là gửi thông điệp ra toàn mạng. Thông điệp tìm kiếm
theo kiểu phát tràn chỉ được chuyển tiếp một số
lần rồi sẽ bị loại bỏ nên không thể đảm
bảo sẽ tìm thấy thông tin có tồn tại trên mạng. Cách tìm kiếm phát tràn khi tìm kiếm
các dữ liệu phổ biến được chia sẻ trên nhiều máy thì tỷ lệ thành công là khá cao nhưng
ngược lại nếu dữ liệu chỉ được chia sẻ trên một vài máy thì xác suất tìm thấy là nhỏ.
Tính chất này là hiển nhiên vì trong mạng ngang hàng không có cấu trúc, không có bất
kỳ mối liên hệ giữa mộ
t máy và dữ liệu nó quản lý trong mạng, do đó yêu cầu tìm
kiếm được chuyển một cách ngẫu nhiên đến một số máy trong mạng. Số lượng máy
trong mạng càng lớn thì khả năng tìm thấy thông tin càng nhỏ. Một nhược điểm khác
của hệ thống này là yêu cầu gửi đi không có định hướng nên một yêu cầu tìm kiếm
thường được chuyển cho một số lượng lớn các máy trong mạng, làm tiêu tốn một
lượng lớn băng thông của mạng và dẫn đến hiệu quả tìm kiếm chung của mạng thấp.
Mạng ngang hàng có cấu trúc đã khắc phục nhược điểm của mạng không cấu trúc

hoặc hàng triệu nút.
+ Khả năng chịu lỗi: hệ thống vẫn có thể làm việc ổn định ngay cả khi có các sự
kiện nút tham gia, rời bỏ mạng hay lỗi xảy ra.
+ Kỹ thuật khóa được sử dụng để đạt được mục đích là m
ỗi nút chỉ cần liên kết
với một số ít các nút khác trong hệ thống, thường là O(logn) với n là số nút tham gia.
Vì vậy sự thay đổi của một nút chỉ ảnh hưởng đến một phần nhỏ của hệ thống mạng.
+ Một số thiết kế bảng băm phân tán có tính bảo mật nhằm chống lại những
người tham gia có ác tâm và cho phép người tham gia giấu danh tính, mặc dù điều này
không phổ biến trong các h
ệ thống mạng ngang hàng chia sẻ tệp tin.
+ Cuối cùng, bảng băm phân tán phải giải quyết những vấn đề cơ bản của các hệ
thống phân tán đó là cân bằng tải, tính toàn vẹn dữ liệu và hiệu năng (cụ thể là đảm
bảo các hoạt động như định tuyến, lưu trữ, truy vấn phải được thực thi nhanh chóng).
2.2.2. Mạng ngang hàng có cấu trúc CHORD
Theo một đánh giá tổng hợp v
ề các thuật toán định tuyến dựa trên bảng băm
phân tán trong các kiến trúc mạng khác nhau như hình tròn (với giao thức Chord), hình
cây, hình hộp (với giao thức CAN)…xét về tính linh hoạt trong việc định tuyến, khả
năng phục hồi trạng thái cũng như khả năng chịu lỗi, kiến trúc hình tròn đều được
đánh giá cao. Vì vậy, kiến trúc Chord thường được sử dụng như là mạng phủ để thực
hiện các cài đặt cả
i tiến việc tìm kiếm trên mạng ngang hàng có cấu trúc.
Mô hình mạng Chord:
Chord được mô tả dưới dạng một vòng tròn và không gian định danh phân bố
đều trên vòng tròn tăng dần theo chiều kim đồng hồ. Nếu gọi N là số bit định danh của
không gian khóa thì mạng Chord có thế chứa tối đa 2N nút. Mỗi nút trên Chord có một
định danh id và có khả năng duy trì liên kết hai chiều với các nút đứng liền trước và
liền sau nó theo chiều kim đồng hồ, tạo thành một mạch liên k
ết vòng. Nút liền trước