ĐẠ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
CHƯƠNG 4. THỰC THI VÀ ĐÁNH GIÁ CHƯƠNG TRÌNH 38
CHƯƠNG 5. KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN TIẾP THEO 44
DANH MỤC HÌNH ẢNH
Hình 1. Cấu trúc hệ thống dịch vụ dựa vào vị trí 4
Hình 2. Một số thiết bị di động sử dụng dịch vụ dựa vào vị trí 5
Hình 3. Mạng diện rộng không dây 6
Hình 4. Mạng cục bộ không dây 7
Hình 5. Mạng cá nhân không dây 7
Hình 6: Xác định vị trí dùng tín hiệu vệ tinh 8
Hình 7. Xác định vị trí dùng dựa vào các trạm sóng đài 9
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 19. 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 20: Minh hoạ việc tạo truy vấn theo ngữ cảnh 34
Hình 21: 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 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àng có cấu trúc là một giải pháp tốt. Bởi vì mạng ngang hàng có cấu trúc có ưu điểm 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 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.
2
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
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à
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í
4
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ó thể
sử dụng để truy cập và hiển thị thông tin. Người dùng có thể nhận thông tin dưới các
dạng như âm thanh, văn bản, hình ảnh... Các thiết bị di động có thể là PDA, Phones,
Laptops... nhưng cũng có thể là các thiết bị định vị gắn kèm với ô tô.
Có nhiều loại thiết bị kết nối với dịch vụ dựa vào vị trí, tuỳ theo sức mạnh và khả
năng lưu trữ của thiết bị, người dùng có thể sử dụng một hoặc nhiều dịch vụ khác nhau.
Các thiết bị dùng dịch vụ dựa vào vị trí có thể được phân loại thành hai loại là thiết bị
đơn nhiệm và thiết bị đa nhiệm.
+ Thiết bị đơn nhiệm: Thường sử dụng các dịch vụ khẩn cấp như còi báo động
hoặc cảnh báo tình trạng khẩn cấp.
+ Thiết bị đa nhiệm: Các thiết bị này đang được nhiều người sử dụng và nó đã
trở thành một phần của cuộc sống chúng ta. Một số thiết bị đa nhiệm trong hình vẽ 2:
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.
Các hệ thống định vị sử dụng vệ tinh chủ yếu dùng để phục vụ cho mục đích quân
sự nên khi dùng trong dân sự thì chúng bị giới hạn về độ chính xác như hệ thống định vị
toàn cầu thì độ chính xác khoảng 15 m. Hiện nay có một số máy thu tín hiệu của hệ
thống định vị toàn cầu đã có thể xác định vị trí chính xác hơn và sai lệch khoảng 3 m.
Tín hiệu của hệ thống định vị toàn cầu bị nhiễu bởi khá nhiều yếu tố như: điều
kiện khí quyển, tín hiệu đi theo nhiều đường, lỗi đồng bộ giữa máy thu và vệ tinh của hệ
thống định vị toàn cầu, thiết bị thu tín hiệu bị che khuất bởi các toà nhà.
+ Định vị dựa vào mạng: Hệ thống này xác định vị trí của người dùng dựa vào các
cột sóng đài.
8
Hình 7. Xác định vị trí dùng dựa vào các trạm sóng đài
1.3.4. Nhà cung cấp ứng dụng và dịch vụ
Nhà cung cấp dịch vụ cung cấp một số các dịch vụ khác nhau cho người dùng và
phản hồi các yêu cầu cung cấp dịch vụ cho người dùng. Các dịch vụ và ứng dụng được
cung cấp như các dịch vụ về tìm vị trí, tìm đường đi dựa trên thông tin mà người dùng
cung cấp hoặc tìm kiếm các thông tin về đối tượng mà người dùng quan tâm (như nhà
hàng, viện bảo tàng, khách sạn, tiệm ăn...)
Thông thường dịch vụ dựa vào vị trí được chia thành hai loại:
+ Dịch vụ kéo về (Pull Services): Là những dịch vụ đáp ứng yêu cầu trực tiếp
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 đó.
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
- Hệ thống có thể cung cấp dịch vụ thời gian thực.
- Người dùng có thể sử dụng dịch vụ mọi lúc, mọi nơi.
+ Vấn đề tìm kiếm thông tin theo vị trí:
Hệ thống dịch vụ tìm kiếm thông tin theo vị trí hiện nay chủ yếu được xây dựng
theo mô hình khách - chủ. Nhược điểm của mô hình này đó là dễ bị quá tải tại máy chủ
trung tâm khi có nhiều người dùng truy cập cùng một thời điểm và khó khăn khi mở
rộng hệ thống.
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.
11
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.
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
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:
14
+ 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
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
bằng cách sử dụng hệ thống bảng băm phân tán (DHT: Distributed Hash Table [6]). Hệ
16
thống này định nghĩa liên kết giữa các nút mạng trong mạng theo một thuật toán cụ thể,
đồng thời xác định chặt chẽ mỗi nút mạng sẽ chịu trách nhiệm đối với một phần dữ liệu
chia sẻ trong mạng. Với cấu trúc này, khi một máy cần tìm một dữ liệu, nó chỉ cần áp
dụng một giao thức chung để xác định nút mạng nào chịu trách nhiệm cho dữ liệu đó và
sau đó liên lạc trực tiếp đến nút mạng đó để lấy kết quả.
Trong mạng ngang hàng có cấu trúc, tài nguyên được phân bố một cách hợp lý để
không có một máy tính nào lưu giữ quá nhiều dữ liệu dẫn đến quá tải thông tin định
tuyến. Do mạng là có cấu trúc nên các thông điệp chuyển đi giữa các máy tính để duy trì
mạng ngang hàng được giảm xuống tối thiểu. Băng thông của mạng được dành nhiều
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,
sẽ lưu một bảng định tuyến gọi là Finger Table, cho phép nút đó định tuyến tới các nút ở
xa. Mỗi dòng trong bảng Finger Table sẽ lưu thông tin về một nút ở xa, gọi là một entry.
Không gian định danh của mạng sử dụng bao nhiêu bit thì Finger Table có bấy nhiêu
entry.
18
Hình 12. Mô hình mạng Chord
Hình trên minh hoạ cho một mạng Chord có 3 nút là 0, 1, 3 và các bảng Finger
Table ứng với mỗi nút, N = 3 bit nên Finger Table có 3 entry. Các trường trong mỗi
entry trong bảng Finger Table của nút n được định nghĩa trong bảng dưới:
Hình 13: Định nghĩa các trường trong bảng định tuyến của Chord
Trong đó các giá trị tại dòng i của bảng được coi như là finger thứ i của nút n.
Thông tin lưu trong bảng cũng bao gồm cả IP và Port của các nút tương ứng. Nút đầu
19
Copyright: Tài liệu đại học ©