ĐẠ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
HÀ NỘI - 2009
ĐẠ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
Sinh viên
Phạm Đình Hậu
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
2.4. Kết luận ............................................................................................................................ 24
CHƯƠNG 3. 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 26
3.1. Mục đích và yêu cầu của tìm kiếm thông tin dựa vào vị trí ............................................ 26
3.2. Giải pháp thực hiện .......................................................................................................... 27
3.2.1. Tạo câu truy vấn phù hợp với ngữ cảnh ................................................................... 27
3.2.2. Biểu diễn dữ liệu theo vị trí ...................................................................................... 27
3.2.3. Chèn dữ liệu vào mạng ngang hàng có cấu trúc ....................................................... 29
3.2.4. Tìm kiếm dữ liệu ....................................................................................................... 30
3.3. Cấu trúc hệ thống ............................................................................................................. 32
3.4. Hoạt động của hệ thống ................................................................................................... 33
Hình 22: 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 23: Minh hoạ mạng ngang hàng trả kết quả cho thiết bị di động 36
Hình 24: Minh hoạ giao diện hiển thị kết quả tìm kiếm thông tin 38
Hình 25: Giao diện hiển thị kết quả trên bản đồ 39
Hình 26: Mô hình thí nghiệm 40
Hình 27: Kết quả thí nghiệm 41
Hình 28: Đồ thị kết quả thử nghiệm 42
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ực và cung cấp các thông tin như dịch vụ gần nhất, theo dõi
phương tiện giao thông, các dịch vụ khẩn cấp. Dịch vụ tìm kiếm thông tin là một dịch
vụ quan trọng của dịch vụ dựa vào vị trí và đang phát triển mạnh.
Tuy hiện nay có nhiều dịch vụ tìm kiếm thông tin nhưng thông tin tìm kiếm được
thường không đúng yêu cầu và không có liên hệ với ngữ cảnh của người dùng. Ngữ
cảnh ở đây là các thông tin cá nhân (tuổi, giới tính, sở thích, lịch làm việc), thông tin
môi trường xung quanh (thời gian trong ngày, mùa trong năm, thời tiết...) và vị trí của
người dùng. Để đáp ứng được nhu cầu của người sử dụng là tìm kiếm thông tin chính
xác và phù hợp với yêu cầu của người dùng thì khoá luận đã xây dựng một hệ thống tìm
kiếm thông tin theo vị trí trong đó thông tin được tìm kiếm dựa trên ngữ cảnh của người
dùng. Hệ thống sẽ cung cấp thông tin một cách tự động cho người dùng bằng cách tạo
truy vấn tìm kiếm tự động từ ngữ cảnh của người dùng. Yêu cầu của hệ thống này là
phải có khả năng tìm kiếm dữ liệu trên quy mô lớn, có tính phân tán và có khả năng mở
rộng cao.
Công nghệ mạng ngang hàng đã phát triển nhanh chóng trên mạng Internet trong
thời gian gần đây với sự xuất hiện của hàng loạt các ứng ngang hàng như Napster,
Gnutella, Freenet, BitTorrent, Edonkey…. Sở dĩ mô hình mạng mạng ngang hàng phát
triển như vậy là vì mô hình này rất phù hợp với tính phân tán của dữ liệu, đồng thời nó
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
trữ và xử lý lớn như PDA, Smart Phone, Pocket PC.... Giá thành của các sản phẩm này
liên tục giảm khiến cho số lượng người dùng sử dụng các thiết bị thông minh này tăng
nhanh chóng. Chính vì số lượng các thiết bị thông minh này tăng nhanh dẫn đến nhu cầu
của người dùng muốn sử dụng các dịch vụ gia tăng trên các thiết bị này lớn. Dịch vụ
dựa vào vị trí là một dịch vụ gia tăng đang phát triển ngày nay. Các ứng dụng của dịch
vụ này rất đa dạng, các ứng dụng này cung cấp cho mọi người các thông tin như vị trí
các rạp chiếu bóng, các phòng nghe nhạc, các bữa tiệc và các thông tin về bản đồ, nhà
hàng, viện bảo tàng, bệnh viện... ở các địa điểm gần mình.
1.2. Tổng quan về dịch vụ dựa vào vị trí
Dịch vụ dựa vào vị trí là dịch vụ cung cấp các thông tin liên quan đến vị trí của
thiết bị di động cầm tay thông qua mạng điện thoại hoặc kết nối không dây. Dịch vụ dựa
vào vị trí cũng có thể được định nghĩa là dịch vụ khai thác các thông tin về vị trí của
thiết bị di động cầm tay. Dịch vụ này có thể cung cấp các thông tin như “Vị trí trạm
ATM (Automatic Teller Machine) gần nhất” hoặc các thông tin về vị trí của các nhà
hàng, quán ăn, các bến xe... ở quanh vị trí của thiết bị di động cầm tay. Các thông tin
này có thể được cung cấp một cách tự động mà không cần bất cứ thao tác yêu cầu nào
của người dùng hoặc người dùng cũng có thể yêu cầu trực tiếp các thông tin mình muốn
tìm và có thể tuỳ chọn tìm kiếm thông tin về một vị trí được chỉ định trên bản đồ số.
Dịch vụ dựa vào vị trí mới xuất hiện gần đây, dịch vụ này tập trung vào cung cấp các
dịch vụ trong phạm vi nhóm người dùng không chuyên và hoạt động trong môi trường
tính toán di động có năng lực tính toán thấp.
Các ứng dụng phổ biến của dịch vụ dựa vào vị trí:
+ Định vị: Dùng để xác định vị trí của một người nào hay vật nào để trả lời cho
câu hỏi đang ở đâu.
+ Di chuyển: Ứng dụng này có thể chỉ dẫn một cách chi tiết làm sao để đi đến 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 đó.
Mobile Phone, Smart Phone, Pocket PC, Laptop hoặc PDA.
Hình 2. Một số thiết bị di động sử dụng dịch vụ dựa vào vị trí
5
+ Đặc điểm của các thiết bị di động:
- Hầu hết các thiết bị di động có tài nguyên tính toán và khả năng xử lý thấp.
- Màn hình hiển thị nhỏ, pin có thời gian sử dụng ngắn, bị ảnh hưởng bởi điều kiện
thời tiết.
- Bị giới hạn về băng thông kết nối.
1.3.2. Mạng kết nối
Thành phần này dùng để truyền dữ liệu, phục vụ các yêu cầu của người dùng và
gửi kết quả cho người dùng.
Mạng kết nối thường được phân chia thành các loại khác nhau tuỳ theo mục đích,
giới hạn về sóng đài (radio) và các tính chất địa lý.
+ 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
6
+ 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
7
- 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 đó.
9
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
hiển thị dưới dạng tin nhắn hoặc hiển thị trên bản đồ để người dùng có thể thấy một
cách trực quan vị trí của thông tin.
10
1.5. Tìm kiếm thông tin dựa vào vị trí
+ Yêu cầu của hệ thống tìm kiếm thông tin theo vị trí là:
- Cung cấp kết quả chính xác với yêu cầu của người dùng và giá thành của dịch vụ
hợp lý.
- Có thể định vị được các thiết bị di động trong phạm vị rộng,
- Với các dịch vụ khác nhau thì có độ ưu tiên khác nhau như với dịch vụ khẩn cấp
thì phải đáp ứng nhanh còn với dịch vụ tìm tiệm ăn, nhà hàng, khách sạn thì có thể ưu
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.
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
Mạng ngang hàng ngày càng trở nên phổ biến trong các ứng dụng chia sẻ trên
mạng. Các mạng ngang hàng đã xuất hiện từ những năm 1980 và phát triển mạnh mẽ
như APANET, Usenet, FidoNet. Hiện nay, với sự tham gia của các công ty thương mại
và phi thương mại như Napster, Gnutella mạng ngang hàng ngày càng lớn mạnh và
được được nhiều người sử dụng. Nhất là hiện nay khi lượng thông tin truyền tải trên
mạng vô cùng lớn, nhu cầu tìm kiếm và chia sẻ thông tin cũng tăng lên. Mạng ngang
hàng được xây dựng giữa các máy tính độc lập có khả năng chia sẻ dữ liệu và tận dụng
tài nguyên để chia sẻ cho các máy tính khác.
2.1. Tổng quan về mạng ngang hàng
2.1.1. Khái niệm mạng ngang hàng
Mạng ngang hàng là một cấu trúc được tạo nên bởi các máy tính liên kết với nhau,
vai trò của mỗi máy tính là như nhau, mỗi máy tính là một phần và duy trì sự tồn tại của
mạng. Các máy tính trong mạng thường xuyên liên lạc với các máy tính khác để ổn định
mạng và chia sẻ dữ liệu với nhau. Mạng ngang hàng có nhiều ứng dụng và ứng dụng
phổ biến nhất là chia sẻ tệp tin, tất cả các dạng tệp tin chia sẻ như âm thanh, hình ảnh,
dữ liệu...
Hình 9: Mô hình mạng ngang hàng
13
Một mạng ngang hàng đúng nghĩa không có khái niệm máy chủ và máy khách hay
nói cách khác tất cả các máy tham gia đều bình đẳng và được gọi là Peer. Peer là một
nút mạng vừa đóng vai trò là máy chủ với các máy khác trong mạng vừa đóng vai trò là
máy khách khi được các máy khác phục vụ mình. Dữ liệu được chứa trên các máy tính
+ Chính vì yêu cầu dịch vụ được đáp ứng một cách tùy biến nên máy yêu cầu dịch
vụ có thể nhận được nhiều kết quả khác nhau khi nó kết nối đến các máy khác nhau
cung cấp cùng một dịch vụ.
+ Các yêu cầu gửi đi có thể không nhận được kết quả trả về vì không có gì đảm
bảo sẽ tồn tại một máy nào đó có khả năng đáp ứng yêu cầu đó.
+ Các tài nguyên có thể biến mất do nút cung cấp tài nguyên có thể ngắt kết nối
bất cứ lúc nào.
2.1.3. Phân loại mạng ngang hàng
Mạng ngang hàng lai ghép
Trong mô hình này, mỗi máy đều được nối với tất cả các máy khác trong mạng,
cách nối này mang đặc điểm của mô hình mạng ngang hàng thuần túy. Tuy nhiên, vẫn
có một máy đóng vai trò máy chủ trung tâm, máy chủ này có nhiệm vụ quản lý các
thông tin chỉ mục.
Hình 10. Hệ thống mạng ngang hàng lai ghép
Những nhược điểm của việc quản lý điều khiển tập trung vẫn tồn tại trong mô hình
mạng này. Nếu máy chủ trung tâm gặp lỗi thì các máy Peer không thể truy cập đến
15
thông tin chỉ mục ở trên máy chủ trung tâm nên không thể tìm kiếm thông tin được. Đại
diện cho mô hình mạng ngang hàng lai ghép là mạng ngang hàng Napster.
Mạng ngang hàng thuần tuý
Trong mạng ngang hàng thuần tuý thì vai trò của các máy trong mạng là ngang
nhau và trong mô hình mạng này thì đã loại bỏ sự tồn tại của các máy chủ tập trung.
Mạng ngang hàng thuần tuý được chia thành hai loại là mạng ngang hàng không có 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ả
hơn cho việc chia sẻ tài nguyên.
Hình 11. Mạng ngang hàng có cấu trúc Chord dạng vòng tròn
Việc tìm kiếm thông tin trong mạng ngang hàng có cấu trúc cũng nhanh hơn trong
mạng ngang hàng không có cấu trúc. Nếu như trong mạng ngang hàng không có cấu
trúc các máy tính gửi thông điệp lan tràn để tìm kiếm thông tin thì trong mạng ngang
hàng có cấu trúc một máy tính chỉ cần gửi thông điệp tìm kiếm qua một số máy tính là
có thể tìm thấy được thông tin có tồn tại trên mạng.
Một số mạng ngang hàng có cấu trúc nổi tiếng bao gồm Chord, CAN, Kademlia,
Pastry và Tapestry.
17
Copyright: Tài liệu đại học ©