Tài liệu Thiết kế và phát triển thuật toán định vị sử dụng cơ sở dữ liệu access points dựa vào tín hiệu wifi 273547

ĐỖ VĂN THÀNH BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƯỜNG ĐẠI HỌC BÁCH KHOA HÀ NỘI ------------------------------------- CHUYÊN NGÀNH KỸ THUẬT TRUYỀN THÔNG ĐỖ VĂN THÀNH THIẾT KẾ VÀ PHÁT TRIỂN THUẬT TOÁN ĐỊNH VỊ SỬ DỤNG CƠ SỞ DỮ LIỆU ACCESS POINTS DỰA VÀO TÍN HIỆU WIFI LUẬN VĂN THẠC SĨ KỸ THUẬT CHUYÊN NGÀNH: KỸ THUẬT TRUYỀN THÔNG KHOÁ 2012B HÀ NỘI - 2014 BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƯỜNG ĐẠI HỌC BÁCH KHOA HÀ NỘI ------------------------------------- ĐỖ VĂN THÀNH THIẾT KẾ VÀ PHÁT TRIỂN THUẬT TOÁN ĐỊNH VỊ SỬ DỤNG CƠ SỞ DỮ LIỆU ACCESS POINTS DỰA VÀO TÍN HIỆU WIFI LUẬN VĂN THẠC SĨ KỸ THUẬT CHUYÊN NGÀNH: KỸ THUẬT TRUYỀN THÔNG Người hướng dẫn khoa học: TS. PHẠM VĂN TIẾN HÀ NỘI - 2014 HVTH: Đỗ Văn Thành MỤC LỤC DANH MỤC BẢNG BIỂU, HÌNH VẼ ...................................................................... 3 LỜI CAM ĐOAN ....................................................................................................... 5 MỞ ĐẦU ..................................................................................................................... 6 CHƯƠNG 1. GIỚI THIỆU VỀ LBS (LOCATION BASE SERVICE) VÀ HỆ THỐNG WPS (WIFI POSITIONING SYSTEM) ...................................................... 8 1.1 LOCATION BASED SERVICE (LBS) ............................................................ 8 1.2 WIFI-BASED POSITIONING SYSTEM ......................................................... 9 1.3 MỘT SỐ ỨNG DỤNG KHẢ QUAN CÓ THỂ TRIỂN KHAI ......................13 1.4 CÁC HỆ THỐNG CÓ LIÊN QUAN ĐÃ ĐƯỢC TRIỂN KHAI TRÊN THẾ GIỚI .......................................................................................................................13 1.5 KẾT LUẬN .....................................................................................................15 CHƯƠNG 2. CƠ SỞ LÝ THUYẾT CỦA HỆ THỐNG WPS (WIFI POSITIONING SYSTEM) ..................................................................................................................16 2.1 Wi-Fi TECHNOLOGY ...................................................................................16 2.2 NGUYÊN LÝ VÀ CÔNG NGHỆ ĐỊNH VỊ SỬ DỤNG SÓNG Wi-Fi .........18 2.2.1 Mô hình mạng ........................................................................................... 18 2.2.2 Network base topology ............................................................................. 19 2.2.3 Terminal base topology ............................................................................ 19 2.2.4 Terminal assisted topology ....................................................................... 20 2.3 CÁC PHÉP ĐO VÀ ỨNG DỤNG CHO CÔNG NGHỆ ĐỊNH VỊ SỬ DỤNG SÓNG Wi-Fi .......................................................................................................... 20 2.3.1 Dựa trên khoảng cách ngắn nhất ............................................................. 20 2.3.2 Phương pháp cell possitioning ................................................................. 21 2.3.3 Dựa trên phương pháp tam giác lượng .................................................... 22 2.3.4 Dựa trên các phép đo góc (triangulation) ................................................ 24 2.3.5 Dựa vào các mô hình nhận biết ................................................................ 26 2.4 CÁC CÔNG CỤ SẼ SỬ DỤNG ..................................................................... 27 2.4.1 Hệ quản trị cơ sở dữ liệu MYSQL ............................................................ 27 2.4.2 Visual studio 2012 .................................................................................... 29 2.4.3. Eclipse ...................................................................................................... 29 2.4.4. Net Surveyor ............................................................................................ 31 2.4.5 Smartphone Samsung Galaxy S2 .............................................................. 32 2.4.6 Laptop Asus A42F..................................................................................... 33 2.5 TRUYỀN THÔNG GIỮA MÁY TÍNH VÀ MOBILE .................................. 33 2.5.1 Giới Thiệu Chung ..................................................................................... 33 1 HVTH: Đỗ Văn Thành 2.5.2 Giới Thiệu Về Socket ................................................................................ 33 2.5.3 Các Thuộc Tính Của Socket ..................................................................... 33 2.5.4 TCP và UDP ............................................................................................. 34 2.5.5 Mô Hình Server và Client ......................................................................... 36 2.5.6. Mô Hình Server/ Client Của Hệ Thống WPS .......................................... 38 2.6 KẾT LUẬN ..................................................................................................... 39 CHƯƠNG 3. PHÂN TÍCH VÀ ĐỀ XUẤT THUẬT TOÁN DỊNH VỊ ................... 40 3.1 PHƯƠNG PHÁP FINGER-PRINT................................................................. 40 3.1.1 Cơ sở lý thuyết............................................................................................. 40 3.1.2 Áp dụng vào đề tài....................................................................................... 44 3.2 PHÂN TÍCH PHÂN BỐ CƯỜNG ĐỘ TÍN HIỆU ACCESS-POINT THEO PHÂN BỐ GAUSS................................................................................................ 45 3.3. ĐÁNH GIÁ CÁC YẾU TỐ ẢNH HƯỞNG TỚI SỰ THAY ĐỔI CƯỜNG DỘ TÍN HIỆU CỦA ACCESS POINTS TẠI MỘT VỊ TRÍ XÁC ĐỊNH............ 51 3.4 ĐỀ XUẤT THUẬT TOÁN ĐỊNH VỊ VÀ ĐÁNH GIÁ THUẬT TOÁN ...... 54 3.4.1 Ý tưởng đề xuất ......................................................................................... 54 3.4.2 Thảo luận về chất lượng bản đồ. .............................................................. 57 3.4.3. Thực hiện thuật toán ................................................................................ 61 3.4.4 Nhận xét về ý tưởng thuật toán ................................................................ 63 3.5 KẾT LUẬN ..................................................................................................... 64 CHƯƠNG 4. THIẾT KẾ HỆ THỐNG ..................................................................... 65 4.1. SƠ ĐỒ HỆ THỐNG ....................................................................................... 65 4.1.1 Khối server................................................................................................ 66 4.1.2. Sơ đồ khối của positioning client( mobile) ............................................. 68 4.2. XÂY DỰNG CƠ SỞ DỮ LIỆU ..................................................................... 72 4.2.1. Xác định tọa độ và địa chỉ MAC của Access Points ................................ 72 4.2.2 Đo đạc độ mạnh yếu cảu tín hiệu tại các điểm tham chiếu ...................... 73 4.2.3 Xử lý dữ liệu ............................................................................................. 74 4.3.4 Đưa dữ liệu vào Database ........................................................................ 76 KẾT LUẬN VÀ ĐỀ XUẤT...................................................................................... 79 TÀI LIỆU THAM KHẢO ......................................................................................... 81 2 HVTH: Đỗ Văn Thành DANH MỤC HÌNH VẼ Hình 1.1: Sơ đồ hệ thống ..................................................................................................... 12  Hình 1.2 Dịch vụ LBS lai ghép các hệ thống của Skyhook................................................ 14  Hình 1.3 Ứng dụng UNIWIDE- định vị sử dụng WIFItại trường đại học New South Wales- Australia. ................................................................................................................. 15  Hình 2.1. (Topology-đồ hình mạng) .................................................................................... 19  Hình 2.2: Tam giác lượng .................................................................................................... 22  Hình 2.3: angle of arrival signal .......................................................................................... 24  Hình 2.4: kết quả AOA ........................................................................................................ 25  Hình2.5: giao diện NetSurveyor .......................................................................................... 32  Hình 2.6 Mô hình TCP/IP .................................................................................................... 35  Hình 2.7: Mô hình Client Server ......................................................................................... 38  Hình 3.1: Hạn chế khi sử dụng công thức Euclid. ............................................................... 45  Hình 3.2 : So sánh phân bố cường độ tín hiệu của Access Points theo phân bố chuẩn ...... 47  Hình 3. 3 : Phương pháp chỉ số và kiểm định bằng Q-Q plot.............................................. 49  Hình 3.4 Các hướng tương đối của anten phát với điện thoại. ........................................... 52  Hình 3.5: Cường độ tín hiệu thu được theo các hướng khác nhau tại một điểm cố định. ... 53  Hình 3.6 : Đối tượng RSSi. ................................................................................................. 54  Hình 3.7: Tập hợp các đối tượng được chọn. ..................................................................... 55  Hình 3.8: Chênh lệch cường độ tín hiệu theo các hướng khác nhau. .................................. 56  Hình 3.9: Cơ sở dữ liệu Accesspoints theo các hướng khác nhau. ...................................... 57  Hình 3.10: Bản đồ vị trí đặt các Accesspoints tại tầng 6. .................................................... 58  Hình 3.11: Phân bố cường độ tín hiệu của AP1. ................................................................. 58  Hình 3.12: Phân bố cường độ tín hiệu của AP2. ................................................................. 58  Hình 3.13: Phân bố cường độ tín hiệu của AP3. ................................................................. 59  Hình 3.14: Phân bố cường độ tín hiệu của AP4. ................................................................. 59  Hình 3.15: Phân bố cường độ tín hiệu của AP5. ................................................................. 60  Hình 3.16: Phân bố cường độ tín hiệu của AP6. ................................................................. 60  Hình 3.17: Lưu đồ thuật toán. .............................................................................................. 62  Hình 3.18: Độ ổn định và độ chính xác của thuật toán định vị. .......................................... 63  Hình 4.1: Sơ đồ hệ thống WPS. ........................................................................................... 65  Hình 4.2 Sơ đồ khối Server.................................................................................................. 66  Hình 4.3 Sơ đồ khối Client .................................................................................................. 68  Hình 4.4 Bản đồ tầng 6 thư viện Tạ Quang Bửu ................................................................. 69  Hình 4.5: Sơ đồ khối database hệ thống. ............................................................................. 72  Hình 4.6: Kết quả đưa dữ liệu cường độ tín hiệu của APs vào database . ........................... 76  Hình 4.7: Thông tin các điểm tham chiếu. ........................................................................... 77  Hình 4.8: Bảng thông tin các Access Points. ....................................................................... 77  Hình 4.9: Bảng độ mạnh tín hiệu tại các điểm tham chiếu. ................................................. 78  3 HVTH: Đỗ Văn Thành DANH MỤC BẢNG BIỂU, HÌNH VẼ Bảng 1.1: Các hệ thống định vị WIFI hiện có. .................................................................... 11  Bảng 1.2: So sánh hiệu năng PDA và Laptop...................................................................... 13  Bảng 3.1: Phương pháp xem xét các giá trị Skewness. ....................................................... 50  Bảng 3.2: Phương pháp kiểm định Kolmogorov-Smirnov và Shapiro-Wilk . .................... 50  Bảng 4.1: Địa chỉ MAC của các APs trong vùng khảo sát. ................................................. 73  4 HVTH: Đỗ Văn Thành LỜI CAM ĐOAN Trước hết tôi xin gửi lời cảm ơn chân thành tới tập thể các thầy cô trường Đại Học Bách Khoa Hà Nội đã tạo ra một môi trường tốt để tôi học tập và nghiên cứu. Xin cảm ơn các thầy cô trong khoa đào tạo sau đại học đã quan tâm đến khóa học này, tạo điều kiện cho các học viên có điều kiện thuận lợi nhất để học tốt. Và đặc biệt tôi xin gửi lời cảm ơn sâu sắc đến thầy giáo TS. Phạm Văn Tiến, thầy đã tận tình chỉ bảo, hướng dẫn và định hướng cho nội dung của luận văn này. Tôi xin cam đoan rằng nội dung của luận văn này là hoàn toàn do tôi tìm hiểu, nghiên cứu và viết ra. Tất cả đều được tôi thực hiện cẩn thận và có sự định hướng của giáo viên hướng dẫn. Tôi xin chịu trách nhiệm với những nội dung trong luận án này. Tác giả ĐỖ VĂN THÀNH 5 HVTH: Đỗ Văn Thành MỞ ĐẦU a) Lý do chọn đề tài Ngày nay dịch vụ dựa trên thông tin về vị trí (Location base service-LBS) đang dần được ứng dụng mạnh mẽ trong đời sống sinh hoạt của con người. Trong đó công nghệ LBS dựa trên sóng WIFI đã và đang trở nên hết sức hấp dẫn, nó cho thấy sự hiệu quả về chi phí cũng như sự tiên lợi của mình nhất là trong lĩnh vực định vị trong nhà (indoor). Nhưng vấn đề quan trọng là phải tìm ra được một thuật toán định vị có độ chính xác và độ ổn định cao, vì vậy tôi đã quyết định chọn đề tài:” Thiết kế và phát triển thuật toán định vị sử dụng cơ sở dữ liệu Access Points dựa vào tín hiệu WIFI” để làm luận văn tốt nghiệp thạc sỹ của mình. b) Mục đích nghiên cứu của luận văn, đối tượng, phạm vi nghiên cứu Phân tích được các yếu tố ảnh hưởng tới phân bố cường độ tín hiệu của Access Points, qua đó chuẩn hóa cơ sở dữ liệu Access Points làm cơ sở để đưa ra thuật toán có độ chính xác và ổn định cao. Đối tượng nghiên cứu của đề tài là hệ thống Access Points được dựng sẵn tại tầng 6, thư viện Tạ Quang Bửu, trường Đại học Bách Khoa Hà Nội. Phạm vi nghiên cứu tập trung vào thiết kế và phát triển thuật toán định vị mới sử dụng cơ sở dữ liệu Access ponts dựa trên tín hiệu WIFI. c) Nội dung chính của luận văn Ngoài lời mở đầu, mục lục, tài liệu tham khảo, luận văn được chia làm 5 chương. - Chương 1: Giới thiệu về LBS (Location Base Service) và hệ thống WPS (WIFI Positioning System) - Chương 2: Cơ sở lý thuyết của hệ thống WPS (WIFI Positioning System) - Chương 3: Phân tích và đề xuất thuật toán định vị - Chương 4 : Thiết kế hệ thống định vị sử dụng cơ sở dữ liệu Access Points - Chương 5 : Kết luận và đề xuất phát triển thuật toán Sau khi hoàn thành đề tài này, ta đã thấy được phân bố cường độ tín hiệu của Access Points không tuân theo phân bố Gauss vì thế nên sử dụng công thức Euclid 6 HVTH: Đỗ Văn Thành để làm cơ sở trong việc tìm kiếm vị trí trong Database, yếu tố hướng tương đối giữa anten phát và anten thu ảnh hưởng trực tiếp đến cường độ tín hiệu nhận được nên phải đưa yếu tố hướng vào trong định vị. d) Phương pháp nghiên cứu Tìm hiểu lý thuyết phân bố cường độ tín hiệu của anten sử dụng trong Access Points. Sử dụng các bài đo để dánh giá chính xác các yếu tố ảnh hưởng tới phân bố cường độ tín hiệu đó. Trên cơ sở của kết quả thực tế chuẩn hóa cơ sở dữ liệu Access Points. Thử nghiệm định vị với thuật toán và cơ sở Access Points vừa xây dựng để đưa ra đánh giá và hướng phát triển của thuật toán. e) Kết luận Định vị không dây (WIFI Positioning System - WPS) là một trong những hướng đi tiềm năng nhất để tận dụng cơ sở hạ tầng rộng lớn, sẵn có của công nghệ WIFI đang phát triển mạnh mẽ tại các thành phố lớn. Với những ứng dụng hấp dẫn và thiết thực như:ứng dụng để tìm đường, dẫn đường, tìm tiện ích xung quanh (nhà hàng, khách sạn, trạm xe buýt…), theo dõi, giám sát đối tượng, cứu hộ, cứu nạn công nghệ định vị sử dụng mạng Wi-Fi không chỉ hứa hẹn sẽ mang đến một kho tàng ứng dụng hữu ích cho người dùng mà còn mang đến một tương lai tươi sáng cho nhà cung cấp dịch vụ. Vì vậy việc nghiên cứu và phát triển một thuật toán định vị không dây có độ chính xác và tính ổn định cao là vấn vô cùng quan trọng. Xin chân thành cảm ơn! 7 HVTH: Đỗ Văn Thành CHƯƠNG 1 GIỚI THIỆU VỀ LBS (LOCATION BASE SERVICE) VÀ HỆ THỐNG WPS (WIFI POSITIONING SYSTEM) 1.1LOCATION BASED SERVICE (LBS) Với sự triển khai rộng khắp các hệ thống di động và mạng không dây, các dịch vụ định vị có thể được triển khai trên các thiết bị di động: máy tính xách tay, điện thoại thông minh, PDA. Có nhiều ứng dụng có thể triển khai dựa vào khả năng định vị như định hướng, theo dõi người và tài sản, dịch vụ an ninh, ứng dụng phối hợp ứng phó tai nạn, phòng chống thiên tai [3,5]. Để cung cấp dịch vụ định vị đáng tin cậy, thời gian thực và độ chính xác vị trí người sử dụng phải chấp nhận được. Do đó, việc phát triển một thuật toán định vị đáp ứng được yêu cầu đó ngày càng được quan tâm. Đối với môi trường ngoài trời, hệ thống định vị toàn cầu (GPS) và định vị tế bào [3,6,7] thường được chọn làm kỹ thuật trong dịch vụ định hướng . Tuy nhiên, các kỹ thuật này không thể được sử dụng trực tiếp trong nhà vì các tín hiệu thường quá yếu. Như vậy, định vị trong nhà sử dụng tín hiệu Wi-Fi trở thành một hướng nghiên cứu phổ biến trong những năm gần đây. Có một số phương pháp định vị trong nhà sử dụng GPS như GPS tương trợ (AGPS) [8], đòi hỏi một kết nối đến máy chủ vị để ước tính vị trí trong nhà có độ chính xác từ 5-50m [8]. Một phương pháp khác được Calibree đề xuất[9] trong đó sử dụng cường độ tín hiệu được phát từ tháp di động để xác định vị trí tương đối của điện thoại di động với vị trí của họ. Ngoài ra, định vị trong nhà còn được thực thi trên điện thoại GSM [10]và CDMA [11] dựa trên việc lấy mẫu tín hiệu. Sai số trung bình của định vị tế bào là 4-5m. Mặc dù cá phương pháp này cho độ chính xác tương đối trong môi trường trong nhà nhưng không đủ để xây dựng dịch vụ dựa trên định vị một cách tin cậy và nó chỉ có thể áp dụng trên điện thoại di động. Ngoài việc sử dụng GPS và mạng tế bào,các dạng công nghệ không dây khác cũng được sử dụng để định vị trong nhà. Đặc biệt, hệ thống định vị sử dụng tín hiệu 8 HVTH: Đỗ Văn Thành băng rộng, hồng ngoại, sóng radio, cảm ứng, hệ thống sóng siêu âm [1,8,12] có thể định vị với độ chính xác cao. Tuy nhiên, những hệ thống yêu cầu thêm cơ sở hạ tầng và cảm ứng, điều này yêu cầu thêm tiền bạc và công sức cũng như hạn chế triển khai trên diện tích rộng. Củng với việc phát triển rộng khắp mạng không dây cục bộ [WIFI], nhiều hệ thống định vị trong nhà sử dụng WIFI để xác định vị trí người sử dụng. Thời gian truyền (TOA)[13] và sai lệch thời gian (TDOA)[1,14] là 2 công nghệ được sử dụng đề định vị nhưng chúng yêu cầu thêm những cài đặt để tăng khả năng đo lường. Do đó, cường độ tín hiệu truyền (RSS) là thuộc tính được sử dụng cho hệ thống định vị WIFI, chúng ta có thể sử dụng các access points (APs) có sẵn cho việc định vị. Luận văn này sẽ trình bày một hệ thống theo dõi và định vị WIFI sử dụng RSS có thể triển khai trên các thiết bị di động với yêu cầu ít tài nguyên. 1.2WIFI-BASEDPOSITIONING SYSTEM WIFI IEEE 802.11b/g là chuẩn sử dụng cho truy cập internet không dây trong nhà. Hoạt động trên băng tần 2.4 GHz băng tần cho công nghiệp, khoa học và y tế với phạm vi 50-100m. Như đã trình bày, RSS có thể dễ dàng thu thập từ các thiết bị tích hợp WIFI, và đó là lý do tại sao WIFI được sử dụng chủ yếu trong hệ thống định vị. Kỹ thuật đánh giá vị trí: Có 3 kỹ thuật chính để xác định vị trí dựa vào RSS[8,17] được liệt kê sau đây: - Tam giác : RSS có thể đổi ra khoảng cách tới AP dựa vào lý thuyết hoặc mô hình lan truyền tín hiệu trên thực nghiệm. Từ đó, với khoảng cách đo được tới ít nhất 3 Aps đã biết vị trí ta có thể đánh giá được vị trí người sử dụng. Phương pháp này mang tính ước lượng vì mô hình suy hao tín hiệu là khó đoán trước được và không đáng tin cậy. - Điểm lân cận: Phương pháp này tìm RSS mạnh nhất của 1 AP xác định và đánh giá vị trí nằm trong vùng phủ sóng của AP này. Phương pháp này chỉ đưa ra vị trí mang tính ước lượng nhưng dễ thực thi. 9 HVTH: Đỗ Văn Thành - Phân tích kịch bản: Phương pháp này thu thập RSS tại vị trí định vị đã biết, bộ các tín hiệu này được gọi là fingerprints. Vị trí được đánh giá thông qua việc so sánh trực tiếp với mẫu tín hiệu trả về của người sử dụng trả về. Phương pháp này được sử dụng hầu hết trong các hệ thống định vị WIFI và cũng là phương pháp định vị và theo dõi được đề xuất trong luận văn này. Bảng 1.1 tổng hợp một vài hệ thống định vị WIFI đã tồn tại và công bố. Nó chỉ ra rằng sử dụng phương pháp fingerprint đạt được độ chính xác tốt nhất trong môi trường trong nhà. Mặc dù Ekahau [18] đạt được độ chính xác tốt nhất, nó sử dụng phương pháp xác suất để tính toán vị trí và yêu cầu khảo sát RSS tại khu vực cần định vị. Thêm vào đó, việc tính toán vị trí được thực hiện trên sever vì tính toán xác suất khó có thể đáp ứng trên thiết bị di động vì yếu tố hiệu năng. Điều đó làm phát sinh những vấn đề trên hệ thống này. Thứ nhất , thiết bị cần được kết nối cùng mạng với sever để có thế thực hiện việc định vị. Thứ hai, vị trí người sử dụng cần được mã hóa trước khi truyền đến thiết vị để đảm bảo tính tính riêng tư của người sử dụng. Sự hướng đến của luận văn này là thiết kế một hệ thống định vị và theo dõi có độ chính xác chấp nhận được và độ phức tạp tính toán có thể thực thi trên các thiết bị di động. Phương án giải quyết yêu cầu cần có 1 server database để lưu trữ dữ liệu fingerprints thu thập được, chỉ yêu cầu tải về thiết bị 1 lần duy nhất, giúp giảm thời gian kết nối đến sever. Hệ thống này tương đối mềm dẻo và không xâm phạm quyền riêng tư của người sử dụng. 10 HVTH: Đỗ Văn Thành Bảng 1.1: Các hệ thống định vị WIFI hiện có. Microsoft Phạm vi Ekahau[18] Inter Place Lab Research and Skyhook’s RADAR[19,20] WPS[21] Trong nhà hoặc Trong nhà hoặc Khu đô thị Vị trí tính toán khu đô thị khu đô thị Thiết bị di động Sever Phương pháp Fingerprinting định vị KNN+ + Fingerprinting+ Viterbi- xác suất Thiết bị di động Tam giác lượng và map like Độ chính xác 3-5m 1-3m 20+m Trình bày vấn đề và mục tiêu: Kịch bản điển hình của một hệ thống định vị WIFI được trình bày trong hình 1.1 gồm có: - Thiết bị di động có trang bị adapter WIFI được người sử dụng cầm và sẽ thu thập RSS có thể dò ta từ các AP trong phạm vi định vị - Các điểm truy cập Aps có thể tìm thấy khắp trong các tòa nhà và vị trí của chúng không cần biết trước. - Một database server lưu trữ fingerprint mà thiết bị di động thu thập được bao gồm thông tin về địa chỉ MAC, SSID và RSS là các thông tin APs phát broadcast tới các thiết bị di động. Luận văn này tập trung vào các vần đề định vị và theo dõi WIFI sử dụng RSS là một bộ giá trị đo lường. Thiết bị di động được người sử dụng cầm và thu thập RSS từ L AP khác nhau có địa chỉ MAC duy nhất và dùng để làm ID. Hệ thống xác định vị trí hiện tại dựa trên RSS trả về và cơ sở dữ liệu fingerprint được đo lường trước đó. Kết quả của luận văn là đề xuất hệ thống định vị và theo dõi WIFI thời gian thực với độ chính xác trung bình và có thể thực thi trên thiết bị di động. 11 HVTH: Đỗ Văn Thành Hình 1.1: Sơ đồ hệ thống Yêu cầu kỹ thuật: Sự biến thiên RSS trong môi trường trong nhà là một thách thức kỹ thuật trong hệ thống định vị WIFI. Có 4 lý do chính cho sự biến đổi RSS . Thứ nhất, là kiến trúc môi trường trong nhà bao gồm các vật cản và nhiễu đa đường của sóng WIFI. Thứ hai, sóng WIFI với băng tần 2.4GHz sẽ bị ảnh hưởng bởi các nguồn sóng khác như điện thoại không dây, sóng bluetooth và sóng vi ba. Ngoài ra sự di chuyển của người cũng ảnh hưởng đến tín hiệu [22]. Và cuối cùng là hướng của thiết bị đo lường là góc giữa anten thu và anten phát do tín hiệu là không đẳng hướng. Trên hết là không thể tìm được mô hình xác suất thể hiện mối quan hệ giữa RSS và vị trí. Do đó, phương pháp fingerprinting sử dụng để biểu thị mối quan hệ RSS và vị trí. Phương pháp này tính toán vị trí bằng cách đối chiếu so sánh tín hiệu RSS hiện tại với fingerprint trong cơ sở dữ liệu được thu thập trong quá trình (training phase). Phương pháp này gặp khó khăn ở việc dữ liệu RSS thu thập được ở 2 thời điểm khác nhau với sự di chuyển của vật thể dẫn đến thay đổi tín hiệu. Những biến đổi RSS cần được xác định để nâng cao độ chính xác của phương pháp định vị này. Một thách thức khác liên quan đến khả năng tính toán của các thiết bị di động. Bảng 1.2 so sánh tốc độ xử lý và bộ nhớ của PDA và Laptop với hiệu suất trung bình. Nó cho thấy các PDA có tốc độ tính toán và bộ nhớ rất hạn chế so với máy tính xách tay. Vì vậy một số các hệ thống định vị có thể thực hiện trên máy tính xách tay nhưng không thể có khả năng sử dụng trên các thiết bị PDA. Các tính toán phức tạp 12 HVTH: Đỗ Văn Thành và sử dụng bộ nhớ lớn được xem xét trong khi thiết kế hệ thống sẽ được lưu ý trong luận văn này. Bảng 1.2: So sánh hiệu năng PDA và Laptop Thiết bị Tốc độ xử lý RAM HP iPAQ hx4700 624 MHz 64MB Dell Inspiron 15 Laptop 2.2 GHz 4 GB 1.3MỘT SỐ ỨNG DỤNG KHẢ QUAN CÓ THỂ TRIỂN KHAI  Hệ thống điều hướng tại trung tâm mua sắm, hướng dẫn khách xem các gian hàng và cung cấp thông tin chi tiết về sản phẩm (chất liệu, giá, sản phẩm đang giảm giá…).  Trong viện bảo tàng, ứng dụng LBS để hướng dẫn lộ trình tham quan, cung cấp các thuyết minh ngay tại vị trí khách quan sát.  Ứng dụng để tìm đường, dẫn đường, tìm tiện ích xung quanh (nhà hàng, khách sạn, trạm xe buýt…) tích hợp trongsmartphone.  Theo dõi, giám sát đối tượng (tracking).  Tìm kiếm trẻ em bị thất lạc trong khu vực trong nhà.  Tìm kiếm các thiết bị bị thất lạc,bị mất trộm.  Ứng dụng trong việc điều khiển robot và xác định vị trí của chúng.  Cứu hộ, cứu nạn. 1.4CÁC HỆ THỐNG CÓ LIÊN QUAN ĐÃ ĐƯỢC TRIỂN KHAI TRÊN THẾ GIỚI 1.4.1 Skyhook project Là 1 trong những công ty hàng đầu về lĩnh vực định vị,Skyhook sử dụng những hệ thống lai ghép như: WPS + GPS, WPS+ IP address, WPS + Cell Tower ID nhằm làm tăng độ chính xác đối với những môi trường không thuận lợi.SKYHOOK đã bỏ ra 1 lượng tài chính và nhân lực đáng kể để thiết kế hệ thống WPS.Công ty này đã thuê hơn 200 nhân viên toàn thời gian làm nhiệm vụ “WARDRIVING “ để lấy thông tin về các Aceess points tại hơn 100 khu đô thị trên toàn thế giới. 13 HVTH: Đỗ Văn Thành WPS + GPS: hai hệ thống này là sự kết hợp hoàn hảo vì nó cân bằng những điểm mạnh và yếu của mỗi hệ thống cho nhau. GPShoạt động hiệu quả ở ngoài trời và những vùng hẻo lánh, trong khi đó tại những đô thị đông đúc hay trong các tòa nhà thì tỏ ra kém hiệu quả. Đó là khi hệ thống WPS phát huy tác dụng. WPS + Cell Tower ID:Các hệ thống định vị sử dụng Cell Tower ID đã được triển khai hơn nửa thập kỷ trở lại đây nhưng độ chính xác của nó vẫn chưa thuyết phục được người sử dụng. Skyhook đã kết hợp WPS + Cell Tower ID để tăng độ chính xác trong các khu đô thị nơi có nhiều nhà cao tầng và đông dân cư. (source:http://www.skyhookwireless.com/howitworks/xps.php) Hình 1.2 Dịch vụ LBS lai ghép các hệ thống của Skyhook. 1.4.2 Navizon Tương tự như SKYHOOK,NAVIZON cũng sử dụng hệ thống định vị lai ghép giữa các hệ thống GPS, Wi-Fi and cellular positioning đểlàm tăng độ chính xác.Hệ thống WPS của Navizon có bản quyền thuộc về Yahoo mobile và năm 2008, Microsoft chọn Navizon làm đối tác trong định vị dùng WIFI và Cell Tower ID. 1.4.3 Các hệ thống WPS tại một số trường đại học Một số nhóm nghiên cứu tại các trường đại học công nghệ trên thế giới đã thiết kế thành công hệ thống định vị sử dụng WIFI-WPS. Trong đó,mộtví dụ điển hình là hệ thốngUniwide WIFI Based Positioning System của trường đại học New South Wales. Hệ Thống cho phép người dung biết được vị trí của mình và của bạn bè khi họ đang ở trong khuôn viên trường hay trong giảng đường. 14 HVTH: Đỗ Văn Thành (Source: Uniwide WIFI Based Positioning System paper from IEEE.COM) Hình 1.3 Ứng dụng UNIWIDE- định vị sử dụng WIFItại trường đại học New South Wales- Australia. 1.5 KẾT LUẬN Do tính chất mới mẻ,có thể ứng dụng cao vào cuộc sống và những ưu điểm nổi trội của hệ thống WPS đã trình bày ở trên, tối và một số bạn đã quyết định nghiên cứu thuật toán và sẽ thiết kế hệ thống định vị sử dụng sóng WIFI- WPS, dùng tầng 6 thư viện Tạ Quang Bửu - Trường Đại Học Bách Khoa Hà Nội để thực hiện trong thực tế. Ứng dụng sau khi hoàn thành sẽ có những chức năng cơ bản sau:  Chạy trên smartphone: Samsung galaxy S2.  Cho phép người dùng sử dụng chức năng định vị để biết được vị trí hiện tại của mình khi đứng trên tầng 6 thư viện TQB.  Vẽ lộ trình người dùng trên bản đồ. 15 HVTH: Đỗ Văn Thành CHƯƠNG 2 CƠ SỞ LÝ THUYẾT CỦA HỆ THỐNG WPS (WIFIPOSITIONING SYSTEM) 2.1 Wi-Fi TECHNOLOGY WIFI(Wireless Fidelity) hay WIFI hay IEEE 802.11 là mộttiêu chuẩn công nghiệp cho việc truyền dữ liệu không dây. WIFI sử dụng sóng điện từ để truyền dữ liệu, hoạt động trong băng thông rộng từ2.4 GHz- 5 GHz. Tần số này cao hơn so với các tần số sử dụng cho điện thoại di động, các thiết bị cầm tay và truyền hình. Tần số cao hơn cho phép tín hiệu mang theo nhiều dữ liệu hơn. Khi truyền đi, sóng radio sẽ trải rộng cùng với đó là sự tăng lên của bán kính vùng phủ sóngvà sự giảm dần độ mạnh của tín hiệu. Một kết nối WIFI sẽ cho chúng ta biết cácthông tin cơ bảnvề độ mạnh của tín hiệu, địa chỉ MAC và can nhiễu. Các chuẩn 802.11: - Chuẩn 802.11b là phiên bản đầu tiên trên thị trường. Đây là chuẩn chậm nhất và rẻ tiền nhất, và nó ít phổ biến hơn so với các chuẩn khác. 802.11b phát tín hiệu ở tần số 2.4 GHz, nó có thể xử lý với tốc độ11 megabit/s, và nó sử dụng mã CCK (complimentary code keying). - Chuẩn 802.11g cũng phát ở tần số 2.4 GHz, nhưng nhanh hơn so với chuẩn 802.11b, tốc độ xử lý đạt 54 megabit/giây. Chuẩn 802.11g nhanh hơn vì nó sử dụng mã OFDM (orthogonal frequency-division multiplexing), một công nghệ mã hóa hiệu quả hơn. - Chuẩn 802.11a phát ở tần số 5 GHz và có thể đạt đến 54 megabit/ giây. Nó cũng sử dụng mã OFDM. Những chuẩn mới hơn sau này như 802.11n còn nhanh hơn chuẩn 802.11a, nhưng 802.11a vẫn chưa phải là chuẩn cuối cùng. - Chuẩn 802.11n cũng phát ở tần số 2.4 GHz, nhưng nhanh hơn so với chuẩn 802.11a, tốc độ xử lý đạt 300 megabit/giây. 16 HVTH: Đỗ Văn Thành Trong việc định vị sử dụng WIFI, khoảng cách từ nguồn phát tới nguồn thu là một yếu tố đóng vai trò then trốt, để tính toán được khoảng cách đó, hai đại lượng RSS (received signal strength) và SNR(signal noise ratio)phải được xác định. Do suy hao trên đường truyền nên càng xa nguồn phát, tín hiệu càng yếu dần, dựa vào tính chất của suy hao cũng có thể xác định được khoảng cách từ vị trí cần xác định tới nguồn phát. Vấn đề chính trong định vị trong nhà dựa trên RSS là xác định mối quan hệ giữa RSS và vị trí, qua đó ước lượng vị trí người dùng dựa trên RSS thu được tại vị trí đó. Có 2 cách tiếp cận để tìm ra mối liên hệ này: sử dụng mô hình lan truyền của tín hiệu và phương pháp đinh vị fingerprinting. Mô hình lan truyền tín hiệu: Kỹ thuật này sử dụng RSS thu thập được bởi thiết bị mobile để ước tính khoảng các của thiết bị từ ít nhất 3 APs đã được biết trước vị trí dựa vào mô hình lan truyền của tín hiệu vô tuyến. Sau đó sử dụng tam giác lượng để có được vị trí của thiết bị Tính chính xác của thiết bị này phụ thuộc rất nhiều vào việc tìm ra 1 mô hình tốt, có thể mô tả tốt nhất các đặc tính của kênh truyền vô tuyến. Tuy nhiên, kênh truyền vô tuyến trong nhà là không ổn định và thay đổi theo thời gian, do tính đa đường trong môi trường trong nhà; ảnh hưởng của sự che chắn, khúc xạ, phản xạ và tán xạ gây bởi các chướng ngại vật và các bức tường; và do sự can thiệp của các thiết bị hoạt động ở cùng tần số (2.4 GHz) theo chuẩn 802.11 b/g WIFI như điện thoại di động, các thiết bị sóng cực ngắn và thiết bị Bluetooth. Có 2 mô hình thường được sử dụng cho kênh lan truyền vô tuyến trong nhà: Mô hình tổ hợp giữa suy hao và che chắn: Mô hình này kết hợp mô hình suy hao và ảnh hưởng của sự che chắn, được giả định là 1 quá trình ngẫu nhiên theo chuẩn lôga. Công suất nhận được từ 1 AP xác định cách d mét được cho bởi công thức: pr [dBm]  p0 [dBm]  10 log10 K  10 log10 17 d   dB d0 HVTH: Đỗ Văn Thành Trong đó: K là hằng số phụ thuộc vòa đặc tính của anten và sự suy hao của kênh truyền, p0 là công suất tín hiệu tại điểm tham chiếu cách d0 so với anten,  là số mũ suy hao – biến đổi trong những môi trường khác nhau ( 2    6 trong môi trường indoor) và dB N (0, 2 ) là một biến ngẫu nhiên Gau.  Mô hình suy hao do yếu tố vật cản Mô hình này gồm các ảnh hưởng của chướng ngại vật giữa bên phát và bên thu. Công suất thu có thể cho bởi: pr [dBm]  p0 [dBm]  10 log10 d nW .WAF, nW  C  d 0 C.WAF, nW  C Trong đó nW là số chướng ngại vật giữa bên phát và bên thu, C là ngưỡng trên – số chượng ngại vật mà không có sự suy hao đáng kể. Và WAF là hệ số suy hao do tường. Hai mô hình thực nghiệm này đòi hỏi phải hiệu chỉnh các thông số, chẳng hạn như số mũ suy hao thay đổi tùy theo môi trường khác nhau. Điều này thường đòi hỏi khảo sát toàn diện về phân bố RSS theo môi trường, dẫn đến rất tốn thời gian. Ngoài ra, các mô hình này giả định RSS được phân bố đẳng hướng từ máy phát. Tuy nhiên điều này không đúng cho trường hợp môi trường trong nhà do sự hiện diện của chướng ngại vật. Hướng của anten của thiết bị di động cũng ảnh hưởng đến RSS, nhưng nó không được đề cập đến trong 2 mô hình. Cuối cùng, vị trí của các APs có thể không được biết trước trong thực tế, cũng như những APs có thể được cài đặt và cung cấp bởi các nhà sản xuất khác nhau. Tất cả những yếu tố trên làm cho các mô hình này không đủ để mô tả quan hệ giữa RSS và vị trí dẫn đến những sai sót trong tính toán vị trí của người dùng. 2.2 NGUYÊN LÝ VÀCÔNG NGHỆ ĐỊNH VỊ SỬ DỤNG SÓNG Wi-Fi 2.2.1 Mô hình mạng Trong định vị sóng Wi-ficó 3 loại đồ hình mạng được sử dụng, đó là:  network-basedtopology.  terminal- basedtopology. 18