›

Đồ án Nghiên cứu phương pháp xác định vị trí nút mạng không dây - Hoàng Anh Sơn

pdf 68 trang huongle 3060
Download
Bạn đang xem 20 trang mẫu của tài liệu "Đồ án Nghiên cứu phương pháp xác định vị trí nút mạng không dây - Hoàng Anh Sơn", để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên

Tài liệu đính kèm:

  • pdfdo_an_nghien_cuu_phong_phap_xac_dinh_vi_tri_nut_mang_khong_d.pdf

Nội dung text: Đồ án Nghiên cứu phương pháp xác định vị trí nút mạng không dây - Hoàng Anh Sơn

  1. Đồ án tốt nghiệp đai học MỤC LỤC BẢNG LIỆT KÊ CÁC TỪ VIẾT TẮT 3 LỜI CẢM ƠN 4 MỞ ĐẦU 5 CHƢƠNG 1: TỔNG QUAN VỀ MẠNG CẢM BIẾN 7 1.1 Giới thiệu về mạng không dây 7 1.2 Cấu trúc của mạng cảm biến 8 1.2.1. Nút cảm biến 8 1.2.2 Mạng cảm biến 10 1.2.3 Cấu trúc đặc trƣng của mạng cảm biến 14 1.3 Thách thức đặt ra đối với mạng cảm biến 18 1.4 Các ứng dụng của mạng cảm biến 19 1.4.1 Ứng dụng quân sự an ninh và thiên nhiên 19 1.4.2 Ứng dụng trong giám sát xe cộ và các thông tin liên quan 20 1.4.3 Ứng dụng cho việc điều khiển các thiết bị trong nhà. 21 1.4.4 Ứng dụng các tòa nhà tự động 21 1.4.5 Ứng dụng trong quá trình quản lý tự động trong công nghiệp 23 1.4.6 Ứng dụng trong y học 24 1.5 Sự khác biệt giữa mạng WSN và mạng truyền thống 24 1.6 Kết luận 25 CHƢƠNG 2: CƠ SỞ LÝ THUYẾT CỦA ĐỊNH VỊ NÚT MẠNG 26 2.1 Pha Phân khoảng 26 2.2 Pha định vị 27 2.3 Một số các hệ thống định vị 31 2.3.1 GPS 31 2.3.2 Active Badge 31 Hoàng Anh Sơn – CT1002 1
  2. Đồ án tốt nghiệp đai học 2.3.3 Active Bat 32 2.3.4 Cricket 32 2.3.5 Radar 32 2.4 Một số hệ thống định vị đƣợc sử dụng trong mạng cảm biến 34 2.4.1 Hệ thống định vị Beacon-based 34 2.4.2 SpotON 34 2.4.3 Calamari 35 2.5 Xác định vị trí các nút trong mạng 35 2.6 Kết luận 36 CHƢƠNG 3: ĐỊNH VỊ NÚT MẠNG TRONG WSN 38 3.1 Tìm kiếm đối tƣợng đơn 38 3.1.1Kỹ thuật điện kế 40 3.1.2 Kỹ thuật RSSI 41 3.1.3 Hệ thống Ferret 43 3.1.4 Kết quả đạt đƣợc 44 3.2 Định vị toàn mạng 49 3.3 Thuật toán xác định vị trí 54 3.4 Kết luận 56 CHƢƠNG 4: GIẢI MỘT SỐ BÀI TOÁN ĐỊNH VỊ HÌNH HỌC 57 4.1 Định vị không ƣớc lƣợng khoảng cách. 57 4.2 Xác định vị trí tƣơng đối bằng ƣớc lƣợng khoảng cách 59 4.3 Xác định trục tọa độ thông qua khoảng cách 61 4.4 Kết luận 66 KẾT LUÂN 67 TÀI LIỆU THAM KHẢO 68 Hoàng Anh Sơn – CT1002 2
  3. Đồ án tốt nghiệp đai học BẢNG LIỆT KÊ CÁC TỪ VIẾT TẮT Từ viết tắt Từ tiếng anh WSN Wireless Sensor Network TDOA Time difference of arrival AOA Angle of arrival TOA Time of arrival ES Evolution Strategies RSSI Received Signal Strength Indicator TOF Time of flight AHLoS Ad-Hoc Localization System RF Radio frequency MAC Media Access Control LESS Localization Using Evolution Strategies in Sensornets ADC Analog to Digital Converter ID Identification GPS Global Positioning System Hoàng Anh Sơn – CT1002 3
  4. Đồ án tốt nghiệp đai học LỜI CẢM ƠN Trong suốt 4 năm học vừa qua với sự giúp đỡ của các thầy cô và giáo viên hướng dẫn về mọi mặt nhất là trong thời gian làm khóa luận tốt nghiệp đã giúp em hoàn thành đúng thời gian quy đinh. Em xin chân thành cảm ơn đến: Bộ môn CNTT và các thầy cô trong khoa đã đã giảng dạy cho em những kiến thức cơ sở làm nền tảng để thực hiện tốt luận văn này. Đặc biêt tôi xin bày tỏ lòng cảm ơn đến PGS.TS Vương Đạo Vy , Khoa Điện Tử Viễn Thông. ĐHCN, ĐHQGHN cùng với thầy giáo Ths Nguyễn Trọng Thể, Khoa Công Nghệ Thông Tin DHDL Hải Phòng đã tận tình giúp đỡ tôi trong quá trình làm luận văn này. Tôi xin cảm ơn đến gia đình, các anh chị và các bạn của tôi đã động viên giúp đỡ tôi trong suốt quá trình làm luận văn. Hải Phòng, Tháng 7 năm 2010 Sinh viên thực hiên Hoàng Anh Sơn Hoàng Anh Sơn – CT1002 4
  5. Đồ án tốt nghiệp đai học MỞ ĐẦU Ngày nay cùng với sự phát triển nhanh chóng của khoa học công nghệ việc nghiên cứu những mạng cho giá thành rẻ tiêu thụ năng lượng ít, đa chức năng mở rộng và hoạt động một cách dễ dàng đang được tập trung nghiên cứu. Trong đó việc nghiên cứu về mạng cảm biến đang được phát triển mạnh mẽ đặc biệt là hệ thống mạng cảm biến không dây (wireless sensor network). Ngày nay có rất nhiều ứng dụng của mạng cảm biến được triển khai. Đó là các ứng dụng theo dõi, tự động hóa, y tế, quân đội và an ninh, Trong một tương lai không xa, các ứng dụng của mạng cảm biến sẽ trở thành một phần không thể thiếu trong cuộc sống con người nếu chúng ta phát huy được hết các điểm mạnh mà không phải mạng nào cũng có được như mạng cảm biến. Tuy nhiên mạng cảm biến đang đối mặt với rất nhiều thách thức đó là vấn đề về năng lượng bị hạn chế. Để duy trì tuổi thọ cho mạng có nhiều cách khác nhau trong đó vấn đề định vị trí chính xác của nút mạng. Nó sẽ giúp giảm một cách đáng kể năng lương cho việc tìm đường và định tuyến do đó sẽ làm tăng khẳ năng sống của mạng. Vì vậy mà bài luận văn tốt nghiệp “ Nghiên cứu phƣơng pháp xác định vị trí nút mạng không dây ” sẽ đi nghiên cứu tổng quan về mạng WSN, tìm hiểu về cách xác định vị trí của nút mạng. Luận văn của em gồm có 4 chương, lời cảm ơn, mở đầu, kết luận và tài liệu tham khảo. Nội dung của các chương được tóm tắt như sau: Chương 1: Tổng quan về mạng cảm biến, chương này sẽ giới thiệu tổng quan về mạng cảm biến không dây, các ứng dụng, thách thức đặt ra với mạng WSN. Chương 2 : Cơ sở lý thuyết, trong chương này sẽ đi nghiên cứu về cơ sở lý thuyết của việc định vi. Tìm hiểu về một số các hệ thống định vị được sử dụng và các hệ thống định vị được sử dụng trong mạng WSN. Hoàng Anh Sơn – CT1002 5
  6. Đồ án tốt nghiệp đai học Chương 3 : Định vị nút mạng trong WSN, trong chương này chúng ta sẽ tìm hiểu các kỹ thuật định vị và thuật toán để xác định vị trí. Chương 4 : Giải một số bài toán định vị hình học, trong chương này ta sẽ đi xét một số ví dụ cụ thể để minh họa cho việc xác định vị trí nút mạng trong mạng WSN Phần kết luận trình bày những vấn đề đã nghiên cứu. Tác giả Hoàng Anh Sơn Hoàng Anh Sơn – CT1002 6
  7. Đồ án tốt nghiệp đai học CHƢƠNG 1: TỔNG QUAN VỀ MẠNG CẢM BIẾN 1.1 Giới thiệu về mạng không dây Trong những năm gần đây, với sự phát triển của Internet, truyền thông và công nghệ thông tin, hệ thống mạng cảm biến đã và đang được phát triển. Nó được triển khai cho nhiều các ứng dụng khác nhau như: theo dõi sự thay đổi của môi trường, khí hậu, giám sát các mặt trận quân sự, phát hiện và do thám việc tấn công bằng hạt nhân, sinh học và hoá học, chuẩn đoán sự hỏng hóc của máy móc, thiết bị, theo dấu và giám sát các bác sỹ, bệnh nhân cũng như quản lý thuốc trong các bệnh viên, theo dõi và điều khiển giao thông Một mạng cảm biến bao gồm số lượng lớn các nút cảm biến được phân bố cả bên trong hiện tượng hoặc phân bố bên cạnh hiện tượng. Vị trí của các nút cảm biến không cần phải thiết kế xác định trước, điều này cho phép các nút cảm biến phân bố ngẫu nhiên trong các địa hình phức tạp. Điều đó cũng có nghĩa là các giao thức của mạng cảm biến và các thuật toán phải có khả năng tự tổ chức. Một đặc điểm quan trọng khác của các mạng cảm biến là khả năng phối hợp giữa các nút cảm biến. Các nút cảm biến được gắn một bộ xử lý bên trong. Thay vì gửi đi số liệu thô tới nút đích, chúng sử dụng khả năng xử lý để thực hiện các tính toán đơn giản và chỉ truyền số liệu đã được xử lý theo yêu cầu. Những ứng dụng của mạng cảm biến đòi hỏi nó phải có những kỹ thuật đặc biệt hơn so với các kỹ thuật áp dụng cho các mạng không dây phi cấu trúc (mạng ad-hoc). Mặc dù nhiều giao thức và giải thuật đã được thiết kế cho những mạng ad hoc không dây truyền thống, nhưng chúng chưa thỏa mãn những đặc tính và yêu cầu ứng dụng của mạng cảm biến. Khi số lượng lớn những nút cảm biến được triển khai mật độ dày thì những nút lân cận phân bố rất gần lẫn nhau, vì vậy truyền thông đa bước nhảy trong mạng cảm biến phải tiêu thụ ít năng lượng hơn truyền thông đơn bước Hoàng Anh Sơn – CT1002 7
  8. Đồ án tốt nghiệp đai học nhảy truyền thống. Hơn nữa, năng lượng phục vụ truyền dữ liệu có thể để ở mức thấp, chủ yếu dành cho các hoạt động chuyển đổi, xử lý. Truyền thông đa bước nhảy cũng khắc phục có hiệu quả vấn đề lan truyền tín hiệu khoảng cách xa trong giao tiếp không dây. Một trong những yêu cầu ràng buộc quan trọng đối với nút cảm biến là mức độ tiêu thụ điện phải thấp. Nguồn cung cấp năng lượng điện cho nút cảm biến là có hạn và nói chung là không thể thay thế. Bởi vậy, trong khi các mạng truyền thống tập trung vào làm sao để đạt được chất lượng dịch vụ cao thì những giao thức mạng cảm biến phải tập trung chủ yếu về sự giữ gìn năng lượng. Chúng phải có những cơ chế cân bằng cho phép lựa chọn việc kéo dài tuổi thọ của mạng hay thông lượng thấp, hoặc độ trễ cao. Các mạng cảm biến gồm có nhiều phương thức thực hiện cảm biến khác nhau như cảm biến địa chấn, cảm ứng từ, cảm biến nhiệt, cảm biến hình ảnh, cảm biến hồng ngoại, cảm biến sóng âm và sóng rađa trong các điều kiện bao quanh đa dạng như: nhiệt độ, độ ẩm, sự chuyển động của phương tiện, điều kiện ánh sáng, sức ép, sự ô nhiễm, mức độ ồn, sự có mặt hoặc không những loại đối tượng nhất định, những đặc trưng hiện thời như tốc độ, hướng, và kích thước một đối tượng. Những nút cảm biến có thể được sử dụng cho cảm biến liên tục, phát hiện sự kiện, định danh sự kiện, cảm biến vị trí, và điều khiển cục bộ thiết bị khởi động. 1.2 Cấu trúc của mạng cảm biến 1.2.1. Nút cảm biến Một nút cảm biến được cấu tạo bởi bốn thành phần cơ bản như hình 1.1 gồm: Bộ phận cảm biến (Sensing Unit), bộ phận xử lý (Processing Unit), bộ phận thu phát (Transceiver Unit) và bộ phận cung cấp năng lượng (Power Unit). Ngoài ra, chúng cũng có thể có những thành phần bổ sung phụ thuộc ứng dụng Hoàng Anh Sơn – CT1002 8
  9. Đồ án tốt nghiệp đai học như: Hệ thống định vị (Location Finding System); Bộ phận phát điện (Power Generator) và bộ phận quản lý di động (Mobilizer). Bộ phận cảm biến thường bao gồm hai bộ phận nhỏ: sensors và bộ phận chuyển đổi tín hiệu tương tự thành tín hiệu số (Analog to Digital Converter - ADCs). Tín hiệu tương tự được sản sinh bởi những thành phần cảm biến dựa vào quan sát hiện tượng được chuyển đổi tới tín hiệu số bởi ADCs, và sau đó được chuyển tới bộ phận xử lý. Bộ phận xử lý thường liên quan đến một bộ phận lưu trữ nhỏ, quản lý những thủ tục làm cho nút cảm biến hợp tác với nhau khác để thực hiện nhiệm vụ cảm biến được định trước. Bộ phận thu phát kết nối nút với mạng. Một trong những thành phần quan trọng của một nút cảm biến là bộ phận cung cấp quản lý năng lượng. Bộ phận này có thể được hỗ trợ bởi một bộ phận tiếp thu năng lượng như pin mặt trời. Nút cảm biến còn có thể có những bộ phận nhỏ khác phụ thuộc từng ứng dụng cụ thể. Hình 1 Thành phần của một nút cảm biến Hầu hết kỹ thuật định tuyến mạng cảm biến và những tác vụ cảm biến đòi hỏi kiến thức định vị vị trí với độ chính xác cao, vì vậy các nút cảm biến thường có hệ thống định vị vị trí. Ngoài ra, tùy thuộc vào ứng dụng, nút cảm biến có thể được trang bị một bộ phận quản lý di động để quản lý chuyển động khi nó được yêu cầu để thực hiện nhiệm vụ định trước. Tất cả những bộ phận cần phải tích hợp trong một mô đun có kích thước nhỏ. Ngoài kích thước, nút cảm biến phải thỏa mãn yêu cầu: Hoàng Anh Sơn – CT1002 9
  10. Đồ án tốt nghiệp đai học Tiêu thụ điện cực nhỏ. Hoạt động được ở mật độ cao. Có chi phí sản xuất thấp và không thiết yếu. Không có định danh và thực hiện tự quản trị. Thích ứng với môi trường. Những nút cảm biến thường là không tác động được, tuổi thọ của một mạng cảm biến phụ thuộc vào tuổi thọ của những nguồn cung cấp năng lượng cho những nút. Vì kích thước giới hạn, năng lượng của nút cảm biến cũng trở thành một tài nguyên khan hiếm. 1.2.2 Mạng cảm biến Như hình 1.1, chúng ta thấy, mạng cảm nhận bao gồm rất nhiều các node cảm biến được phân bố trong một trường cảm biến. Các node này có khả năng thu thập dữ liệu thực tế, sau đó chọn đường (thường là theo phương pháp đa bước nhảy) để chuyển những dữ liệu thu thập này về node gốc. Node gốc liên lạc với node quản lý nhiệm vụ thông qua Internet hoặc vệ tinh. Hình 1.1 Phân bố node cảm biến trong trường cảm biến Việc thiết kế mạng cảm nhận như mô hình trong Hình 1.1 phụ thuộc vào nhiều yếu tố như: Hoàng Anh Sơn – CT1002 10
  11. Đồ án tốt nghiệp đai học Khả năng chịu lỗi: Một số các node cảm biến có thể không hoạt động nữa do thiếu năng lượng, do những hư hỏng vật lý hoặc do ảnh hưởng của môi trường. Khả năng chịu lỗi thể hiện ở việc mạng vẫn hoạt động bình thường, duy trì những chức năng của nó ngay cả khi một số node mạng không hoạt động. Khả năng mở rộng: Khi nghiên cứu một hiện tượng, số lượng các node cảm biến được triển khai có thể đến hàng trăm nghìn node, phụ thuộc vào từng ứng dụng mà con số này có thể vượt quá hàng trăm nghìn node. Do đó cấu trúc mạng phải có khả năng mở rộng để phù hợp với từng ứng dụng cụ thể. Giá thành sản xuất: Vì mạng cảm nhận bao gồm một số lượng lớn các node cảm biến nên chí phí mỗi node là rất quan trọng trong việc điều chỉnh chi phí mạng. Do vậy chi phí cho mỗi node cảm biến phải giữ ở mức thấp. Tích hợp phần cứng: Vì số lượng node cảm biến trong mạng là nhiều nên node cảm biến cần phải có các ràng buộc phần cứng sau: kích thước nhỏ, tiêu thụ năng lượng ít, chi phí sản xuất thấp, thích ứng với môi trường, có khả năng tự cấu hình và hoạt động không cần sự giám sát. Môi trường hoạt động: Các node cảm biến thường là khá dày đặc và phân bố trực tiếp trong môi trường (kể cả môi trường ô nhiễm, độc hại hay dưới nước, ) => node cảm biến phải thích ứng với nhiều loại môi trường và sự thay đổi của môi trường. Các phương tiện truyền dẫn: Ở mạng cảm nhận, các node được kết nối với nhau trong môi trường không dây, môi trường truyền dẫn có thể là sóng vô tuyến, hồng ngoại hoặc những phương tiện quang học. Để thết lập được sự hoạt động thống nhất chung cho các mạng này thì các phương tiện truyền dẫn phải được chọn phù hợp trên toàn thê giới. Hoàng Anh Sơn – CT1002 11
  12. Đồ án tốt nghiệp đai học Cấu hình mạng cảm nhận: Mạng cảm nhận bao gồm một số lượng lớn các node cảm biến, do đó phải thiết lập một cấu hình ổn định. Sự tiêu thụ năng lượng: Mỗi node cảm biến được trang bị nguồn năng lượng giới hạn. Trong một số ứng dụng, việc bổ sung nguồn năng lượng là không thể thực hiện. Vì vậy thời gian sống của mạng phụ thuộc vào thời gian sống của node cảm biến, thời gian sống của node cảm biến lại phụ thuộc vào thời gian sống của pin. Do vậy, hiện nay các nhà khoa học đang nỗ lực tìm ra các giải thuật và giao thức thiết kế cho node mạng nhằm tiết kiệm nguồn năng lượng hạn chế này. * Kiến trúc giao thức mạng cảm nhận Hình 1.2. Kiến trúc giao thức của mạng cảm biến Kiến trúc giao thức áp dụng cho mạng cảm nhận được trình bày trong hình 1.2. Kiến trúc này bao gồm các lớp và các mặt phẳng quản lý. Các mặt phẳng quản lý này làm cho các node có thể làm việc cùng nhau theo cách có hiệu quả nhất, định tuyến dữ liệu trong mạng cảm nhận di động và chia sẻ tài nguyên giữa các node cảm biến.  Lớp vật lý: có nhiệm vụ lựa chọn tần số, tạo ra tần số sóng mang, phát hiện tín hiệu, điều chế và mã hóa tín hiệu. Hoàng Anh Sơn – CT1002 12
  13. Đồ án tốt nghiệp đai học  Lớp liên kết số liệu: có nhiệm vụ ghép các luồng dữ liệu, phát hiện các khung dữ liệu, cách truy cập đường truyền và điều khiển lỗi. Vì môi trường có tạp âm và các node cảm biến có thể di động, giao thức điều khiển truy nhập môi trường (MAC) phải xét đến vấn đề công suất và phải có khả năng tối thiểu hóa việc va chạm với thông tin quảng bá của các node lân cận.  Lớp mạng: quan tâm đến việc chọn đường số liệu được cung cấp bởi lớp truyền tải  Lớp truyền tải: giúp duy trì luồng số liệu nếu ứng dụng mạng cảm nhận yêu cầu. Lớp truyền tải chỉ cần thiết khi hệ thống có kế hoạch được truy cập thông qua mạng Internet hoặc các mạng bên ngoài khác.  Lớp ứng dụng: tùy theo nhiệm vụ cảm biến, các loại phần mềm ứng dụng khác nhau có thể được xây dựng và sử dụng ở lớp ứng dụng.  Mặt phẳng quản lý công suất: điều khiển việc sử dụng công suất của node cảm biến. Ví dụ:  node cảm biến có thể tắt bộ thu sau khi nó nhận được một bản tin để tránh tạo ra các bản tin giống nhau.  Khi mức công suất của node cảm biến thấp, nó sẽ phát quảng bá sang các node cảm biến bên cạnh thông báo rằng mức năng lượng của nó thấp và nó không thể tham gia vào quá trình định tuyến. Công suất còn lại được giành cho nhiệm vụ cảm biến.  Mặt phẳng quản lý di chuyển: có nhiệm vụ phát hiện và đăng ký sự chuyển động của các node. Từ đó có thể xác định xem ai là node hàng xóm của mình.  Mặt phẳng quản lý nhiệm vụ: có nhiệm vụ cân bằng và và sắp xếp nhiệm vụ cảm biến giữa các node trong một vùng quan tâm. Tuy nhiên không Hoàng Anh Sơn – CT1002 13
  14. Đồ án tốt nghiệp đai học phải tất cả các node trong vùng đó đều thực hiện nhiệm vụ cảm biến tại cùng một thời điểm. 1.2.3 Cấu trúc đặc trƣng của mạng cảm biến 1.2.3.1. Cấu trúc phẳng Trong cấu trúc phẳng (flat architecture) (hình 1.3), tất cả các nút đều ngang hàng và đồng nhất trong hình dạng và chức năng. Các nút giao tiếp với gốc qua multihop sử dụng các nút ngang hàng làm bộ tiếp sóng. Với phạm vi truyền cố định, các nút gần sink hơn sẽ đảm bảo vai trò của bộ tiếp sóng đối với một số lượng lớn nguồn. Giả thiết rằng tất cả các nguồn đều dùng cùng một tần số để truyền dữ liệu, vì vậy có thể chia sẻ thời gian. Tuy nhiên cách này chỉ có hiệu quả với điều kiện là có nguồn chia sẻ đơn lẻ, ví dụ như thời gian, tần số Hình 1.3: Cấu trúc phẳng của mạng cảm biến Hoàng Anh Sơn – CT1002 14
  15. Đồ án tốt nghiệp đai học 1.2.3.2. Cấu trúc tầng Trong cấu trúc tầng (tiered architecture) (hình 1.4), các cụm được tạo ra giúp các tài nguyên trong cùng một cụm gửi dữ liệu single hop hay multihop ( tùy thuộc vào kích cỡ của cụm) đến một nút định sẵn, thường gọi là nút chủ (cluster head). Trong cấu trúc này các nút tạo thành một hệ thống cấp bậc mà ở đó mỗi nút ở một mức xác định thực hiện các nhiệm vụ đã định sẵn. Hình 1.4: Cấu trúc tầng của mạng cảm biến Trong cấu trúc tầng thì chức năng cảm nhận, tính toán và phân phối dữ liệu không đồng đều giữa các nút. Những chức năng này có thể phân theo cấp, cấp thấp nhất thực hiện tất cả nhiệm vụ cảm nhận, cấp giữa thực hiện tính toán, và cấp trên cùng thực hiện phân phối dữ liệu (hình 1.4). Hoàng Anh Sơn – CT1002 15
  16. Đồ án tốt nghiệp đai học Hình 1.5: Cấu trúc mạng phân cấp chức năng theo lớp. Mạng cảm biến xây dựng theo cấu trúc tầng hoạt động hiệu quả hơn cấu trúc phẳng, do các lý do sau: Cấu trúc tầng có thể giảm chi phí chi mạng cảm biến bằng việc định vị các tài nguyên ở vị trí mà chúng hoạt động hiệu quả nhất. Rõ ràng là nếu triển khai các phần cứng thống nhất, mỗi nút chỉ cần một lượng tài nguyên tối thiểu để thực hiện tất cả các nhiệm vụ. Vì số lượng các nút cần thiết phụ thuộc vào vùng phủ sóng xác định, chi phí của toàn mạng vì thế sẽ không cao. Thay vào đó, nếu một số lượng lớn các nút có chi phí thấp được chỉ định làm nhiệm vụ cảm nhận, một số lượng nhỏ hơn các nút có chi phí cao hơn được chỉ định để phân tích dữ liệu, định vị và đồng bộ thời gian, chi phí cho toàn mạng sẽ giảm đi. Mạng cấu trúc tầng sẽ có tuổi thọ cao hơn cấu trúc mạng phẳng. Khi cần phải tính toán nhiều thì một bộ xử lý nhanh sẽ hiệu quả hơn, phụ thuộc vào thời gian yêu cầu thực hiện tính toán. Tuy nhiên, với các nhiệm vụ cảm nhận cần hoạt động trong khoảng thời gian dài, các nút tiêu thụ ít năng lượng phù hợp với yêu cầu xử lý tối thiểu sẽ hoạt động hiệu quả Hoàng Anh Sơn – CT1002 16
  17. Đồ án tốt nghiệp đai học hơn. Do vậy với cấu trúc tầng mà các chức năng mạng phân chia giữa các phần cứng đã được thiết kế riêng cho từng chức năng sẽ làm tăng tuổi thọ của mạng. Về độ tin cậy: mỗi mạng cảm biến phải phù hợp với với số lượng các nút yêu cầu thỏa mãn điều kiện về băng thông và thời gian sống. Với mạng cấu trúc phẳng, qua phân tích người ta đã xác định thông lượng tối ưu của mỗi nút trong mạng có n nút là W ,trong đó W là độ rộng băng tần của n kênh chia sẻ. Do đó khi kích cỡ mạng tăng lên thì thông lượng của mỗi nút sẽ giảm về 0. Việc nghiên cứu các mạng cấu trúc tầng đem lại nhiều triển vọng để khắc phục vấn đề này. Một cách tiếp cận là dùng một kênh đơn lẻ trong cấu trúc phân cấp, trong đó các nút ở cấp thấp hơn tạo thành một cụm xung quanh trạm gốc. Mỗi một trạm gốc đóng vai trò là cầu nối với cấp cao hơn, cấp này đảm bảo việc giao tiếp trong cụm thông qua các bộ phận hữu tuyến. Trong trường hợp này, dung lượng của mạng tăng tuyến tính với số lượng các cụm, với điều kiện là số lượng các cụm tăng ít nhất phải nhanh bằng n . Các nghiên cứu khác đã thử cách dùng các kênh khác nhau ở các mức khác nhau của cấu trúc phân cấp. Trong trường hợp này, dung lượng của mỗi lớp trong cấu trúc tầng và dung lượng của mỗi cụm trong mỗi lớp xác định là độc lập với nhau. Tóm lại, việc tương thích giữa các chức năng trong mạng có thể đạt được khi dùng cấu trúc tầng. Đặc biệt người ta đang tập trung nghiên cứu về các tiện ích về tìm địa chỉ. Những chức năng như vậy có thể phân phối đến mọi nút, một phần phân bố đến tập con của các nút. Giả thiết rằng các nút đều không cố định và phải thay đổi địa chỉ một cách định kì, sự cân bằng giữa những lựa chọn này phụ thuộc vào tân số thích hợp của chức năng cập nhật và tìm kiếm. Hiện nay cũng đang có rất nhiều mô hình tìm kiếm địa chỉ trong mạng cấu trúc tầng. Hoàng Anh Sơn – CT1002 17
  18. Đồ án tốt nghiệp đai học 1.3 Thách thức đặt ra đối với mạng cảm biến Để WSN thực sự trở nên rộng khắp trong các ứng dụng thì một số thách thức và trở ngại chính cần vượt qua: Lưu trữ dữ liệu: Các cảm biến lấy mẫu từ môi trường liên tục. Với khả năng lưu trữ hạn chế của các cảm biến trên mạng dữ liệu không được lưu trữ vĩnh viễn. Dữ liệu được lén, lọc, tổng hợp từ các nút, và các dữ liệu cũ phải được xóa đi. Dữ liệu mà muốn lưu trữ trên mạng phải chuyển tiếp đến máy chủ trung tâm. Vấn đề về năng lượng: Vấn đề năng lượng là vấn đề quan trọng của mạng camr biến, khi mà mạng có quy mô lớn việc giám sát và cung cấp năng lượng cho mạng là không thể thực hiện. Sử dụng các thuật toán, kỹ thuật để bảo đảm bảo năng lượng tiêu thụ ít nhất có thể. Khả năng chịu lỗi: Một số các nút cảm biến có thể không hoạt động nữa do thiếu năng lượng, do những hư hỏng vật lý hoặc do ảnh hưởng của môi trường. Khả năng chịu lỗi thể hiện ở việc mạng vẫn hoạt động bình thường, duy trì những chức năng của nó ngay cả khi một số nút mạng không hoạt động Định vị: Sử dụng mạng không dây để xác định vị trí vị trí hay theo dõi các sự kiện đang là vấn đề đang được quan tâm hiện nay. Nếu sử dụng GPS thì vấn đề năng lượng và chi phí là rất khó khăn. Vì vậy mà vấn đề là làm thế nào để xác định được vị trí là vấn quan trọng. Khả năng mở rộng: Khi nghiên cứu một hiện tượng, số lượng các nút cảm biến được triển khai có thể đến hàng trăm nghìn nút, phụ thuộc vào từng ứng dụng con số này có thể vượt quá hàng triệu. Do đó cấu trúc mạng mới phải có khả năng mở rộng để có thể làm việc với số lượng lớn các nút này. Hoàng Anh Sơn – CT1002 18
  19. Đồ án tốt nghiệp đai học An ninh: Các thông tin về nhiệt độ đối với ứng dụng giám sát môi trường đường như vô hại nhưng việc giữ bí mật thông tin là rất quan trọng. Các hoạt động của một toà nhà có thể thu thập được dễ dàng bằng cách lấy thông tin về nhiệt độ và ánh sáng của toà nhà đó. Những thông tin này có thể được sử dụng để sắp xếp một kế hoạch tấn công vào một công ty. Do đó, WSN cần có khả năng giữ bí mật các thông tin thu thập được. Trong các ứng dụng an ninh, dữ liệu bảo mật trở nên rất quan trọng. Không chỉ duy trì tính bí mật, nó còn phải có khả năng xác thực dữ liệu truyền. Sự kết hợp tính bí mật và xác thực là yêu cầu cần thiết của cả ba dạng ứng dụng. Việc sử dụng mã hoá và giải mã sẽ làm tăng chi phí về năng lượng và băng thông. Dữ liệu mã hoá và giải mã cần được truyền cùng với mỗi gói tin. Điều đó ảnh hưởng tới hiệu suất ứng dụng do giảm số lượng dữ liệu lấy từ mạng và thời gian sống mong đợi. 1.4 Các ứng dụng của mạng cảm biến Ngày nay sự phát triển của Internet, thông tin vô tuyến và kỹ thuật thông tin đã tạo lên sự phát triển đầy tiềm năng của mạng cảm biến.Chúng ta sẽ xem xét kỹ một số ứng dụng như sau để hiểu rõ sự cần thiết của mạng cảm biến không dây. Các mạng cảm biến có thể bao gồm nhiều loại cảm biến khác nhau như cảm biến động đất, cảm biến từ trường tốc độ lấy mẫu thấp, cảm biến thị giác, cảm biến hồng ngoại, cảm biến âm thanh, radar mà có thể quan sát vùng rộng trong các điều kiện khác nhau. 1.4.1 Ứng dụng quân sự an ninh và thiên nhiên Trong phản ứng với các dịch bệnh, thảm họa thiên nhiên thì một số lượng lớn các node cảm biến được thả từ trên cao xuống, mạng cảm biến sẽ cho ta biết vị trí sống sót vùng nguy hiểm giúp cho giám sát có các thông tin chính xác đảm bảo hiệu quả cho công tác tìm kiếm. Việc sử dụng mạng cảm biến còn giúp con Hoàng Anh Sơn – CT1002 19
  20. Đồ án tốt nghiệp đai học người làm việc ở những nơi điều kiện khác nghiệt, nguy hiểm đến tính mạng. Ứng dụng trong an ninh là phát hiện xâm nhập và truy bắt tội phạm. Mạng cảm biến quân sự phát hiện và có các thông tin về sự di chuyển của đối phương, chất nổ và các thông tin khác. Phát hiện và phân loại các loại hóa chất, sinh hóa, sóng vô tuyến, phóng xạ hạt nhân. Giám sát sự thay đổi khí hậu của rừng. Giám sát xe cộ trên đường. Giám sát an ninh trong các khu vực dân cư, thương mại. Theo dõi biên giới kết hợp với vệ tinh. Hình 1.2: Ứng dụng WSN trong an ninh quốc gia. 1.4.2 Ứng dụng trong giám sát xe cộ và các thông tin liên quan Mục tiêu của các hệ thống này là thu thập thông tin qua các cảm biến, xử lý và lưu trữ tại trung tâm và sử dụng nó cho các trường hợp cần thiết. Hệ thống được lắp đặt dọc các đường chính nó có tác dụng thu thập các thông tin như mật độ xe cộ, tắc nghẽn giao thông, số lượng xe, lưu lượng xe. Mạng theo dõi liên tục cung cấp các thông tin theo thời gian thực. Các thông tin thu được dùng để điều phối giao thông và cho các mục đích khác. Hoàng Anh Sơn – CT1002 20
  21. Đồ án tốt nghiệp đai học 1.4.3 Ứng dụng cho việc điều khiển các thiết bị trong nhà. Ứng dụng của WSN nó cung cấp việc điều khiển bảo quản các thiết bị trong nhà và giám sát an ninh. Hinh 1.7: Ứng dụng trong điều khiển các thiết bị trong nhà. Các node cảm biến được lắp đặt trên các thiết bị, vị trí cần thiết sau đó nối thành mạng truyền dữ liệu về node trung tâm. 1.4.4 Ứng dụng các tòa nhà tự động Ứng dụng trong điều khiển quản lý, kiểm soát an ninh Quản lý nhiều hệ thống cùng lúc như quản lý nhân viên, điện, nhiệt độ, ánh sáng, gắn các chíp lên các thiết bị từ đó có thể điều khiển chỉ bằng cuộc điện thoại hay bằng việc kích đúp chuột. Hoàng Anh Sơn – CT1002 21
  22. Đồ án tốt nghiệp đai học Hinh 1.8: Ứng dụng trong tòa nhà tự động Ví dụ như những nơi công cộng như hành lang, cầu thang, những nơi có không gian lớn hoặc những nơi không cần sự chiếu sáng thường xuyên, việc bật sáng thường xuyên sẽ gây ra tình trạng lãng phí điện, làm giảm tuổi thọ của bóng đèn. Vì vậy chúng ta có thể sử dụng thiết bị cảm biến hồng ngoại để tự động điều khiển bật tắt các thiết bị. Các cảm biến hồng ngoại được đặt ngay tại nơi cần chiếu sáng, trong vùng quét. Khi có người đi qua cảm biến hồng ngoại sẽ nhận biết và truyền tín hiệu về bộ điều khiển trung tâm để điều khiển bật tắt thiết bị. Thời gian bật tắt được tùy biến cài đặt đảm bảo sự chiếu sáng tiện nghi. Do đó việc lắp đặt hệ thống cảm biến không những đảm bảo tính tiện lợi, hiện đại mà còn nâng cao tính hiệu quả tiết kiệm điện, nhất là các tòa nhà lớn. Hoàng Anh Sơn – CT1002 22
  23. Đồ án tốt nghiệp đai học Hinh 1.9:Tắt bật điện tự động ở hành lang 1.4.5 Ứng dụng trong quá trình quản lý tự động trong công nghiệp Ứng dụng gồm có việc quản lý, điều khiển, hiệu xuất và an toàn trong các hoạt động công nghiệp. Các cảm biến được đặt trong môi trường làm việc để giám sát quá trình làm việc và các sự cố xẩy ra Các dữ liệu sẽ được truyền về trung tâm để những người quản lý có những biện pháp kịp thời. Hình 1.10 Ứng dụng trong công nghiệp. Hoàng Anh Sơn – CT1002 23
  24. Đồ án tốt nghiệp đai học 1.4.6 Ứng dụng trong y học Hiện nay công nghệ thông tin cũng được ứng dụng rất nhiều trong y học vào việc chuẩn đoán, chăm sóc sức khỏe, đối phó với các dịch bệnh, và việc gắn trực tiếp các thiết bị lên người bệnh nhân để đo đạc thường xuyên các thông tin về huyết áp, nhịp tim, Giúp cho các bệnh viện rút ngắn được thời gian điều trị và chuẩn đoán chính xác hơn đồng thời giúp các bác sĩ điều trị cho bệnh nhân một cánh hiệu quả. Hình 1.11: Ứng dụng trong y tế. 1.5 Sự khác biệt giữa mạng WSN và mạng truyền thống Qua phân tích và tìm hiểu ta có thể thấy được sự khác biệt cơ bản của WSN và mạng truyền thống như sau. Số lượng nút cảm biến trong một mạng cảm biến lớn hơn nhiều lần so với những nút trong mạng ad-hoc. Các nút cảm biến thường được triển khai với mật độ dày hơn. Hoàng Anh Sơn – CT1002 24
  25. Đồ án tốt nghiệp đai học Những nút cảm biến dễ hỏng, ngừng hoạt động. Topo mạng cảm biến thay đổi rất thường xuyên. Mạng cảm biến chủ yếu sử dụng truyền thông quảng bá (broadcast) trong khi mà đa số các mạng ad hoc là điểm - điểm (point-to-point). Những nút cảm biến có giới hạn về năng lượng, khả năng tính toán và bộ nhớ. Những nút cảm biến có thể không có định danh toàn cầu (global ID). 1.6 Kết luận Trong chương này chúng ta đã tìm hiểu tổng quan về mạng cảm nhận WSN, cấu trúc và các ứng dụng của nó đã cho thấy sự phát triển của mạng cảm biến và tầm quan trọng đối với cuộc sống của chúng ta. Với sự phát triển như vũ bão của của khoa học công nghệ thì lĩnh vực mạng cảm biến sẽ có những ứng dụng mới. Hoàng Anh Sơn – CT1002 25
  26. Đồ án tốt nghiệp đai học CHƢƠNG 2: CƠ SỞ LÝ THUYẾT CỦA ĐỊNH VỊ NÚT MẠNG Trong đồ án này chúng ta sẽ đi sâu vào việc tìm hiểu định vị vị trí của nút mạng. Việc định vị nút mạng là một trong những vấn đề được quan tâm nhiều trong những năm gần đây[7]. Trong mạng cảm biến thì tài nguyên hạn chế và tỷ lệ lỗi cao thì có nhiều thách thức đặt ra trong quá trình định vị nút mạng. Giá thành của hệ thống định vị cùng với việc hiệu chỉnh và độ chịu lỗi của mạng cảm biến là vấn đề cần được giải quyết. Có rất nhiều thách thức đặt ra đối với mạng cảm biến nhưng một trong các thách thức quan trọng mà đồ án của em đi sâu vào giải quyết đó là việc xác định vị trí của nút mạng. Việc xác định vị trí chính xác của nút mạng nó sẽ giúp ích vào việc định tuyến, tiết kiệm năng lượng từ đó duy trì tuổi thọ cho nút mạng và toàn mạng. Một số các ví dụ về ứng dụng cần biết vị trí của các nút mạng. Để xác định định chất lượng phủ sóng trong mạng cảm biến, vị trí của các nút phải được biết đến. Khi sử dụng định tuyến bằng đồ thị, các nút phải biết vị trí của chúng để xác định hướng để chuyển tiếp thông điệp. Trong các sự kiện phát hiện hoặc theo dõi các mục tiêu, các cảm biến phải biết được vị trí của chúng để tính toán sự di chuyển. Để giúp hướng dẫn qua một cánh đồng, các cảm biến phải biết được vị trí. Hầu hết các kỹ thuật định vị bao gồm hai thao tác. Trong giai đoạn đầu, phải xác định được khoảng cách hoặc góc đo giữa các điểm và các đối tượng cần tìm. Giai đoạn đầu được gọi là phân khoảng. Trong giai đoạn thứ hai, những khoảng cách và góc đo được kết hợp để tạo ra vị trí của đối tượng. Pha này là được gọi là pha đinh vị. 2.1 Pha Phân khoảng Hoàng Anh Sơn – CT1002 26
  27. Đồ án tốt nghiệp đai học Một số các kỹ thuật[1,7] định vị trí của nút mạng được sử dụng cho giai đoạn khác nhau, bao gồm: 1. Cường độ tín hiệu nhận(RSSI): Một nút nhận được thông điệp về cường độ tín hiệu đến. Sử dụng mối quan hệ là cường độ tỷ lệ nghịch với bình phương khoảng cách để ước tính khoảng cách giữa các nút. 2. Tăng theo công suất truyền: Biết được mối quan hệ giữa công suất và khoảng cách tối đa giữa các nút mạng có thể truyền cho phép tăng công suất truyền. Khi thông điệp mà được nghe thấy thì khoảng cách tối đa giữa các nút có thể được suy ra. 3. Thời gian đến (ToA): Việc sử dụng thời gian truyền tín hiệu là một phương pháp để xác định khoảng cách giữa các nút mạng. Sự khác biệt thời gian đến (TDOA) được sử dụng để so sánh tín hiệu nhiều lần. 4. Góc đến (AoA): đo góc giữa hai nút mạng có thể được thực hiện ở các nút được trang bị ăng-ten mảng rất tốn kém. 2.2 Pha định vị Tùy thuộc vào phương pháp được sử dụng, một kỹ thuật định vị nút mạng phù hợp được áp dụng trong giai đoạn thứ hai. Các chiến lược định vị nút mạng sau đây đã được đề xuất: 1. Phép đo ba cạnh tam giác: Đây là một chiến lược phổ biến được sử dụng khi mà khoảng cách giữa các điểm và đối tượng được xác định sẵn. Khi khoảng cách giữa đối tượng và ba điểm đã cho được biết thì vị trí của đối tượng x cần tìm được tính là giao điểm của ba vòng tròn (Hình 2.1). Hoàng Anh Sơn – CT1002 27
  28. Đồ án tốt nghiệp đai học Hình 2.1: Phép đo ba cạnh tam giác 2. Vùng giao nhau: Kỹ thuật phép đo ba cạnh tam giác hoạt động tốt khi ba đường tròn giao nhau tại một điểm duy nhất. Nhưng điều này rất ít khi xẩy ra khi mà sử dụng ước lượng khoảng pha. Cho ví dụ là khi tăng công suất truyền thì các giá trị tối đa có thể được sử dụng để ước tính khoảng cách. Đối tượng được đặt vào miền đồ thị giao nhau của ba đường tròn (Hình 2.2). Hoàng Anh Sơn – CT1002 28
  29. Đồ án tốt nghiệp đai học Hình 2.2: Định vị bằng vùng giao nhau. 3. Phép đạc tam giác: Phương pháp này là hữu ích khi mà góc giữa hai đối tượng được biết đến. Giả sử P1,P2 là hai đối tượng được biết và X là đối tượng cần tìm. Từ P1,P2 ta có thể đo được góc a1,a2 với khoảng cách Sx được biết thì có thể tính được ax, S1,S2. Hình 2.3: Phép đạc tam giác 4. Khẳ năng tối đa: Khi người ta sử dụng ước lượng phân khoảng thì miền giao nhau có thể là rỗng. Điều này sẽ xuất hiện nếu ít nhất ước lượng là quá nhỏ. Một phương pháp giải bài toán này là chọn điểm cho định vị đã cho với tổng số lỗi nhỏ nhất giữa các phép đo và khoảng cách. Hình 2.4 ước lượng khoảng cách (d1, d2, d3) được thực hiện giữa đối tượng và ba điểm (P1, P2, P3). Các lỗi (e1, e2, e3) được tính bằng cách sử dụng khoảng cách Euclide và các ước lượng miền. Hoàng Anh Sơn – CT1002 29
  30. Đồ án tốt nghiệp đai học Hình 2.4: Định vị bằng khẳ năng tối đa. Một vấn đề của việc định vị là tìm vị trí của tất cả các đối tượng trong một mạng lưới cảm biến cho vị trí của một nhóm nhỏ các nút và ước lượng vùng giữa các nước láng giềng. Giải pháp cho vấn đề định vị chỉ đơn giản là trang bị cho mỗi nút thiết bị GPS của riêng mình. Chiến lược này là khả thi trong một số các ứng dụng, nhưng nó bị một số hạn chế của GPS như nó không hoạt động trong nhà hoặc khi dòng tín hiệu bị chặn bởi các tòa nhà cây cối, Quy mô, chi phí và tiêu thụ điện năng của một máy thu GPS là các yếu tố tạo nên sự khó khăn trong việc trang bị cho tất cả các nút trong mạng cảm biến WSN. Vì vậy chúng ta sẽ đi nghiên cứu để phát triển thế hệ máy thu với chi phí và năng lượng tiêu thụ thấp. Trong chương III tôi sẽ trình bày một số kỹ thuật tìm kiếm và xác định vị trí đối tượng bằng kỹ thuật RSSI và kỹ thuật tiến hóa được mô tả trong hệ thống Ferret và hệ thống LESS. Hệ thống định vị phổ biến nhất là hệ thống GPS nó sử dụng thời gian phát sóng radio giữa các vệ tinh nhưng nó có hạn chế là chỉ làm việc ngoài trời. Hầu hết các hệ thống định vị xác định vị trí khi mà biết một số vị trí và khoảng cách. Các hệ thống này đều dựa trên cơ sở hạ tầng. Chính điều này đã dẫn đến hai vấn đề: 1. Hệ thống không có quy mô lớn. Hoàng Anh Sơn – CT1002 30
  31. Đồ án tốt nghiệp đai học 2. Khó khăn trong việc định vị cảm biến trong mạng ad-hoc. 2.3 Một số các hệ thống định vị Một loạt các chiến lược và công nghệ được áp dụng để xác định vị trí hiện tại của nút cảm biến. Trong phần này tôi sẽ mô tả một số hệ thống định vị được sử dụng như GPS, Active Badge, Active Bát, Cricket, và radar. Trong phần tiếp theo chúng tôi sẽ tìm hiểu về kỹ thuật định vị nút mạng sử dụng trong mạng cảm biến. 2.3.1 GPS Hệ thống định vị toàn cầu ( Global Positioning System viết tắt là GPS) gồm 24 vệ tinh (quay quanh quỹ đạo trái đất) quay quanh trái đất khoảng 12.000 dặm trên bề mặt. Đã triển khai năm 1993, các vệ tinh được trang bị các đồng hồ nguyên tử chính xác trong vòng một phần tỷ của một giây, nó quay quanh quỹ đạo của trái đất trong vòng 24h. Hệ thống định vị GPS được phát triển và vận hành bởi Bộ Quốc phòng Hoa Kỳ, GPS được biết đến cho các ứng dụng theo dõi. Để tìm các vĩ độ và kinh độ của một của một người thì độ trễ của tín hiệu từ ba vệ tinh GPS được sử dụng để tính toán. Để tính toán độ cao chính xác nhất, một vệ tinh GPS thứ tư là cần thiết cho việc tính toán. Hệ thống này là chính xác trong vòng 1-3m trong vòng 90-95% thời gian. Hệ thống này không thể được sử dụng trong nhà và ở ngoài trời vì nó bị cản trở bởi chướng ngại vật. 2.3.2 Active Badge Được giới thiệu vào năm 1992, Active Badge là hệ thống xác định vị trí trong nhà đầu tiên được nghiên cứu và phát triển. Nó được phát triển tại phòng thí nghiệm Olivetti, mà bây giờ là AT & T Cambridge. Để xác định vị trí mỗi người, mỗi người trong hệ thống được xác định vị trí nhờ đeo một huy hiệu nhỏ bằng hồng ngoại. Sử dụng tín hiệu khuếch tán hồng ngoại, huy hiệu phát ra một người dùng duy nhất trên toàn cầu ID này sẽ được phát sau mười giây hoặc theo yêu cầu. Một máy chủ trung tâm thu thập các tín hiệu từ bộ cảm biến được phân phối trong mỗi tế bào, trong cả tòa nhà. Độ chính xác của hệ thống này là chính Hoàng Anh Sơn – CT1002 31
  32. Đồ án tốt nghiệp đai học xác là ở mức độ phòng. Hệ thống này có khó khăn khi gặp ánh sáng huỳnh quang hoặc là ánh sáng mặt trời. Phạm vi hồng ngoại được giới hạn trong vài mét vì vậy nó chỉ phù hợp cho các phòng có diện tích nhỏ. Phương pháp beacon là cần thiết được phát triển cho việc định vị trí trong các phòng lớn hơn. 2.3.3 Active Bat Active Bat là hệ thống sử dụng thời gian siêu âm của tín hiệu bay cung cấp độ chính xác hơn nhiều so với hệ thống Active Badge. Được giới thiệu vào năm 1999 bởi AT & T, hệ thống này sử dụng sóng ngắn tương tự như sóng siêu âm của những con dơi. Việc truy vấn đến hệ thống được thực hiện bằng cách sử dụng sóng radio tầm ngắn. Một con dơi phát ra sóng siêu âm tới trần nhà sóng khi đến trần nhà thì phản trở lại. Sự chính xác của hệ thống là trong vòng 9cm trong vòng 95% thời gian. Khi lắp ở trần nhà, điều này gây ra những hạn chế như khả năng mở rộng và khó triển khai. Chi phí lắp đặt của hệ thống là một trở ngại cho hệ thống này. 2.3.4 Cricket Được giới thiệu bởi AT & T nghiên cứu vào năm 2000 để bổ sung cho hệ thống Active Bat, hệ thống Cricket định vị trí sử dụng những tín hiệu siêu âm. Trong Cricket, các thiết bị thực hiện các tính toán để xác định vị trí. Bằng cách này, hệ thống này trở thành phân cấp và nhiều hơn nữa khả năng mở rộng. Nếu không có một máy chủ tập trung, thì vị trí một đối tượng của đối tượng trở nên riêng tư. Hạn chế của cách tiếp cận này là nó sẽ đặt gánh nặng của việc tính toán trên các đối tượng. Hệ thống Cricket định vị chính xác đối tượng trong phạm vi 1.2*1.2m2 trong 100% thời gian. 2.3.5 Radar Một nhóm nghiên cứu Microsoft giới thiệu hệ thống toàn định vị trong nhà rộng lơn vào năm 2000 được gọi là radar. Hệ thống được dựa trên chuẩn IEEE 802.11 đó là một chuẩn phổ biến cho các mạng không dây trong việc định vị trong nhà. Hệ thống radar cung cấp khả năng thực hiện, cũng như phân tích Hoàng Anh Sơn – CT1002 32
  33. Đồ án tốt nghiệp đai học một cảnh thực hiện. Hệ thống này sử dụng cơ sở hạ tầng của trạm cơ sở đã có làm môi trường cho mạng không dây. Các trạm cơ sở đo cường độ tín hiệu và tỷ lệ tín hiệu nhiễu để thực hiện việc định vị. Hệ thống cho độ chính xác trong vòng 3m với 50% thời gian trong khi hệ thống phân tích có độ chính xác trong vòng 4,3m với 50% thời gian. Phép phân tích phải xác định trước độ dài dữ liệu tín hiệu của nó để có thể xây dựng lại dữ liệu nếu môi trường thay đổi. Hạn chế lớn để hệ thống này là tất cả các đối tượng mà bạn muốn xác định vị trí phải hỗ trợ chuẩn 802.11 và được trang bị với một giao diện mạng không dây. Có rất nhiều hệ thống định vị bằng cảm biến. Hightower và Borriello đã đưa ra những khảo sát trong lĩnh vực này. Bảng 1 đưa ra một bản tóm tắt một số hệ thống định vị và công nghệ mà sử dụng. Hệ thống Nơi phát triển Công nghệ Giải thích GPS Bộ quốc phòng Sử dụng 24 vệ Chính xác trong vòng Hoa Kỳ tinh 1-5m trong 95-99% thời gian Active Badge AT&T Sử dụng tín hiệu Chính xác trong phòng Cambridge hồng ngoại Active Bat AT&T Research Sử dụng chuyến Chính xác trong 9cm bay siêu âm trong 95% thời gian Cricket AT&T Research Tín hiệu siêu âm Bổ xung cho hệ thống Active Badge định vị trong vòng 1.44 m2 với 100% thời gian Radar Microsoft Tín hiệu radio Độ chính xác trong Research theo Chuẩn IEEE vòng 4.3m với 50% 802.11 thời gian Bảng 1: Một số hệ thống định vị Hoàng Anh Sơn – CT1002 33
  34. Đồ án tốt nghiệp đai học 2.4 Một số hệ thống định vị đƣợc sử dụng trong mạng cảm biến Trong phần này chúng ta sẽ đi tìm hiểu về một số hệ thống định vị được sử dụng trong mạng cảm ứng không dây. Chúng ta sẽ đi phân tích những hạn chế và những mặt tích cực của từng phương pháp. 2.4.1 Hệ thống định vị Beacon-based Hệ thống định vị bằng dẫn đường (beacon) được giới thiệu và phát triển bởi các nhà nghiên cứu từ UCLA và USC vào năm 2000. Hệ thống được sử dụng năm Radiometrix RPC 418 radio gói điều khiển mô-đun. Bốn trong số đó được đặt trong góc của một khu vực ngoài trời 10 x 10m. Những module này, hoặc đèn hiệu, phục vụ như là điểm tham chiếu và liên tục truyền các gói tin với ID là duy nhất của chúng trong vòng hai giây. Các module khác được sử dụng như một máy thu. Nó lắng nghe cho các thông điệp từ cảnh báo và quyết định mà mô-đun đã được kết nối căn cứ vào tỷ lệ phần trăm thông điệp mà nó nhận được. Ví dụ, nếu người nhận nghe nói 90% của thông điệp từ một đèn hiệu thì có nghĩa là kết nối đã thành công. Hệ thống tính toán các vị trí bằng việc tìm ra lỗi của giao điểm của các đèn hiệu. Nó đã đưa ra một lỗi trong phạm vi 1,83m và mất 41,9 giây để thiết lập kết nối. Để làm cho hệ thống mạnh mẽ hơn, cảnh báo vị trí thích nghi được điều tra. Có các cảnh báo tín hiệu liên tục được phát ra là nhược điểm lớn cho hệ thống này. 2.4.2 SpotON Hệ thống định vị bằng SpotON được nghiên cứu và phát triển bởi Đại học Washington và Intel vào năm 2001. Hệ thống SpotON đã được tạo ra với ý tưởng cảm biến vị trí mạng ad-hoc. Để làm điều này các nút không nhất thiết phải có cơ sở hạ tầng mà nó đã có như ở hầu hết trong các hệ định vị. Các thẻ SpotON được gắn vào bất cứ thứ gì của hệ thống định vị. Các gói vô tuyến dẫn đường đến đích của nguồn chuẩn tại mội khoảng thời gian. Các thẻ đo lường chỉ báo cường độ tín hiệu nhận được (RSSI) khi nghe các cảnh báo. Một mô hình thu-hiệu chuẩn cụ thể được sử dụng với các RSSI để ước tính khoảng cách Hoàng Anh Sơn – CT1002 34
  35. Đồ án tốt nghiệp đai học từ nút chuyển. Đặt một máy phát 50 cm từ nút để được hiệu chuẩn và có nó truyền tải 100 gói hoàn thành việc hiệu chuẩn. Con người và các đối tượng có thể được đặt liên quan đến một hoặc khác hoặc cơ sở hạ tầng đối tượng có thể được sử dụng để tận dụng vị trí dữ liệu. Độ chính xác của hệ thống phụ thuộc vào kích thước của cụm thẻ. 2.4.3 Calamari Hệ thống định vị được phát triển như một dự án chính tại Đại học Berkeley California vào năm 2002. Được xây dựng với cảm biến Berkeley MICA, hệ thống Calamari ước lượng khoảng cách giữa các nút bằng cường độ tín hiệu nhận RSSI và thời gian bay của âm thanh (TOF). Các phần cứng TOF có nhược điểm là tiêu thụ năng lượng nhiều hơn cũng như chi phí bổ sung của các phần cứng là lớn. Các lợi thế của kỹ thuật này là nó ước tính khoảng cách chính xác hơn so với việc sử dụng mỗi cường độ tín hiệu nhận RSSI. Các nút truyền gửi đồng thời tín hiệu sóng ngắn RF và tín hiệu âm thanh. Các nút nhận so sánh thời gian đến của hai tín hiệu. Bởi vì ánh sáng và âm thanh đi ở tốc độ khác nhau, sự khác biệt thời gian đến (TDOA) cho phép hệ thống tính toán khoảng cách của hai nút. Chuẩn hóa vĩ mô của hệ thống thể hiện chuẩn hóa khung như là bài toán đánh giá thông số. Kỹ thuật này đã giúp giảm thiểu sai sót trung bình từ 74,6% xuống 10,1% mà không cần hiệu chuẩn. Trong ba hệ thống định vị được sử dụng trong mạng cảm biến không dây có điểm mạnh và hạn chế của nó. Nhiều vấn đề liên quan đến chủ đề này vẫn không được giải quyết. Một số những thách thức sẽ được giải quyết trong luận văn này. Trong Chương III, chúng tôi trình bày hệ thống định vị Ferret, trong đó sử dụng hai kỹ thuật khác nhau RSSI và tăng công suất truyền. Tiếp theo, chúng ta sẽ xác định vị trí của tất cả các nút trong một mạng cảm biến không dây. 2.5 Xác định vị trí các nút trong mạng Các vấn đề của việc tìm kiếm vị trí của tất cả các nút trong một mạng cảm biến không dây cho vị trí của một tập hợp con của các nút đã được tiếp cận bởi Hoàng Anh Sơn – CT1002 35
  36. Đồ án tốt nghiệp đai học nhiều nhà nghiên cứu. Một hệ thống AHLoS (Hệ thống định vị Ad-Hoc) cho rằng các nút đèn hiệu biết được vị trí của chúng. Các nút còn lại trong hệ thống được coi là chưa biết và nó sẽ cố gắng xác định vị trí của các nút còn lại. Các nút phát quảng bá vị trí của nó, một nút không biết trong vùng có nhiều hơn hoặc bằng 3 tín hiệu dẫn đường (beacons) thì việc đánh giá vị trí của nó sẽ làm giảm thiểu lỗi. Một kỹ thuật lặp đi lặp lại là phép đo đa giác được sử dụng để xử lý việc định vị của tất cả các nút trong hệ thống. Độ chính xác của AHLoS phụ thuộc vào năng lực xử lý của CPU, năng lượng tiêu thụ và mạch phần cứng. Tỷ lệ các cảnh báo cần thiết để phép đo đa giác được thực hiện hợp tác vẫn còn tương đối cao. Có nhiều thuật toán định vị khác nhau nhưng nó luôn bao gồm hai việc chính: Ước tính vị trí và lặp đi lặp lại sàng lọc. Giai đoạn sàng lọc lặp đi lặp lại khoảng 25 lần tại mỗi nút và gửi vị trí của nó cho tất cả các nước láng giềng. Quá trình này phải được lặp đi lặp lại khi topo của mạng thay đổi. Mặc dù kỹ thuật này cung cấp kết quả định vị chính xác, nhưng nó đòi hỏi việc sử dụng năng lượng trong mỗi node khi nó phát sóng liên tục vị trí của nó, trong khi năng lượng một trong những nguồn tài nguyên quý giá cho các nút trong mạng cảm biến. Tại Chương III, chúng tôi trình bày phương pháp phát hiện ra vị trí tập trung mà vấn tiết kiệm năng lượng. Sau khi lập dự toán khoảng cách giữa các nút hàng xóm thì việc định vị và chuyển tiếp dữ liệu này đến một nút cảm biến và các thông tin liên quan là cần thiết. Bởi vì việc loại bỏ các thông tin làm năng lượng tiêu thụ cho mạng sẽ giảm đi và do đó sẽ làm tăng thời gian sống của mạng. Có hai sai sót trong kỹ thuật định vị là sai sót trong việc ước lượng khoảng cách và ngay cả khi khoảng cách được biết chính xác, sai sót trong tính toán tọa độ toàn cầu. 2.6 Kết luận Chương này chúng ta đã đi nghiên cứu về cơ sở lý thuyết của việc định vị. Tìm hiểu về phương pháp định vị nút trong mạng cảm biến bằng cường độ tín hiệu nhận RSSI, tăng theo công suất truyền, thời gian đến, góc đến. Tùy từng phương pháp mà có các chiến lược định vị khác nhau. Chúng ta cũng đi tìm hiểu Hoàng Anh Sơn – CT1002 36
  37. Đồ án tốt nghiệp đai học một số các hệ thống định vị được hiện có và nghiên cứu một số hệ thống định vị được sử dụng trong mạng cảm biến. Qua đó cho ta thấy được những mặt hạn chế và những mặt tích cựu của từng phương pháp. Hoàng Anh Sơn – CT1002 37
  38. Đồ án tốt nghiệp đai học CHƢƠNG 3: ĐỊNH VỊ NÚT MẠNG TRONG WSN 3.1 Tìm kiếm đối tƣợng đơn Trong chương này chúng tôi trình bày cách xác định vị trí của các đối tượng đơn, ví dụ như máy laptop, máy video. Ferret đã phát triển hệ thống định vị nút trong mạng wireless networked sensors (WSN)[1]. Hệ thống gồm cơ sở hạ tầng của các nút đã biết nó đáp ứng các đèn hiệu cần tìm. Các nút được sử dụng trong Ferret được làm bằng Mica, thế hệ thứ hai cảm biến không dây thông minh được phát triển ở Đại học Berkeley California. Hình 3.1 Nút mạng làm bằng Mica Mica được thương mại hóa bởi bơi Crossbow. Nó chưa bộ xử lý ATMEL 4 MHz với tầng số 916MHz. Với vấn đề hạn chế về không gian lưu trữ và năng lương tiêu thụ pin AA, chính điều này làm cho các lập trình viên phải nghiên cứu sâu sắc về vấn đề này. Các nút có 51 chân cho phép kết nối với nhiều mạng cảm biến khác nhau. Nó hỗ trợ hệ điều hành như TinyOS là hệ điều hành rất nhỏ, mã nguồn mở, tiêu thụ năng lương ít được nghiên cứu và phát triển bởi UC Berkeley[2]. Một số các khía cạnh về phần mềm hệ thống Ferret gồm: 1. Hệ thống điện kế. 2. Hệ thống cảm nhận cường độ tín hiệu nhận RSSI. Hoàng Anh Sơn – CT1002 38
  39. Đồ án tốt nghiệp đai học 3. Hiệu chỉnh môi trường. Hình 3.2 minh họa giao diện người dùng hệ thống. Các đầu vào được sử dụng là ID của nút ( số hiệu điện kế hoặc cường độ tín hiệu nhận ). Trong biểu đồ các nút là các ID là nút hạ tầng những nút này hiểu rõ ID của mình và hiểu được vị trí của chúng. Tọa độ của nút cần tìm được đưa vào khi lỗi định vị xẩy ra trong quá trình tính toán và kiểm thử. Hình 3.2: Giao diện hệ thống Ferret. Hệ thống phải được thiết lập các quan hệ giữa các nút và khoảng cách giữa nút và tín hiệu mà nó nhận được. Mối quan hệ này khác nhau giữa các môi trường khác nhau. Ví dụ trong nhà máy hay ngoài trời. Khi hệ thống Ferret di chuyển từ môi trường này sang môi trường khác thì công cụ hỗ trợ môi trường được thiết lập mối quan hệ khoảng cách cho môi trường cụ thể. Đối với hệ đo điện kế công cụ môi trường đáp ứng những khoảng giao tiếp ở trong các mức công suất truyền cho trước đầu ra từ môi trường này. Hoàng Anh Sơn – CT1002 39
  40. Đồ án tốt nghiệp đai học Bảng 2: Mối quan hệ giữa khoảng cách và năng lượng. Bảng trên được tao ra một cách linh động nhờ chạy công cụ môi trường ở những môi trương khác nhau. Thuật toán sử dụng hệ hiệu chỉnh được chỉ ra trong hình 3.3. Hình 3.3: Thuật toán công cụ hiệu chỉnh. 3.1.1Kỹ thuật điện kế Trong phần thứ hai ta sẽ mô tả chi tiết về hệ điện kế và hệ cường độ đã cho. Cả hai kỹ thuật đều truy vấn từ trạm gốc đến đối tượng thông qua các nút hạ tầng. Trong kỹ thuật đo điện kế thì đối tượng(nút di dộng ) truyền đèn hiệu tại nút công suất thấp nhất và lắng nghe sự đáp lại từ các nút hạ tầng. Tăng công suất của nút lên trong mỗi lần truyền. Cứ như vậy cho đến khi đối tượng nhận được ba đáp ứng nó sẽ chuyển tiếp dữ liệu vào nút cơ sở để tính toán vị trí dựa vào phép đo đạc tam giác. Kỹ thuật này được minh họa trong hệ thống Ferret như hình 3.4. Các đường tròn biểu thị các nút hạ tầng thông qua ID. Vòng quay của các vòng tròn được từ bảng đáp ứng khi mỗi công suất được gửi ví dụ như nút 7 nhận được khi giá trị của điện kế đo được là 95 nút này có thể dò được trong khoảng 1.5m. Hoàng Anh Sơn – CT1002 40
  41. Đồ án tốt nghiệp đai học Hệ thống Ferret tập trung vào giao của các đường trong được đáp ứng khi ba nút trả lời. Nó tìm kiếm miền giao nhau và sử dụng định vị nhờ bộ tiên đoán vị trí(điểm x). Hình 3.4: Kết quả của hệ thống Ferret. 3.1.2 Kỹ thuật RSSI Khoảng cách biết trước và cường độ tín hiệu có quan hệ với nhau, bước đầu tiên của kỹ thuật này là tiến hành một số thực nghiệm. Mối quan hệ cần được thiết lập một hàm có thể tính toán dựa trên cường độ tín hiệu nhận RSSI. Hinh 3.5 chỉ ra kết quả của thí nghiệm này trong đó có 5 mẫu giá trị cường độ tín hiệu nhận RSSI tương ứng với các khoảng cách khác nhau. Trong một miền nhỏ các khoảng cách mà chúng tôi quan tâm khi mối quan hệ tuyến tính được thiết lập với tỷ lệ là 0.796. Hoàng Anh Sơn – CT1002 41
  42. Đồ án tốt nghiệp đai học Hình 3.5: Đo khoảng cách bằng RSSI Phương pháp sử dụng cường độ tín hiệu nhận gửi một chuỗi 5 tín hiệu công suất truyền đầy đủ. Các nút hạ tầng đáp ứng lại đầy đủ các tín hiệu mà chúng nghe thấy. Nút di động ghi lại số hiệu ID và giá trị cường độ tín hiệu cho tất cả các gói tin nhận. Nó tính toán cường độ tín hiệu cho mỗi láng giềng khi nghe và xác định ba láng giềng gần nhất bằng cách tìm kiếm giá trị trung bình lớn nhất với kỹ thuật đo điện kế nó chuyển tiếp dữ liệu về trạm cơ sở để tính toán vị trí. Để tính toán vị trí tiên đoán hãy quan tâm tới điểm (xa,ya). Điểm láng giềng bất kỳ là (xi,yi) lỗi là Ei ( Ai là khoảng cách chính xác, Di là khoảng cách ước tính từ cường độ tín hiệu RSSIi). Ei = | Ai – Di | 2 2 Ei = | (yi ya ) (xi xa ) - Di | Kỹ thuật RSSI ươc lượng vị trí bằng không gian trạng thái được kiểm tra và quyết định điểm mà có lỗi ít nhất. Tổng các lỗi có thể được tính toán bằng cách kết hợp các lỗi từ ba lỗi láng giềng. 3 Esum Ei i 1 Hoàng Anh Sơn – CT1002 42
  43. Đồ án tốt nghiệp đai học 3.1.3 Hệ thống Ferret Thực tế có 5 chương trình liên quan cùng làm việc trong hệ thống, Sau đây là là tóm tắt mô tả từ mỗi chương trình và vai trò của nó trong hệ thống theo dõi được giải thích dưới đây[1]. 1.Các nút định tuyến cố định: Việc định tuyến nó sẽ lắng nghe thông điệp gửi đến chúng sẽ thực hiện một trong hai tác vụ phụ thuộc vào gói tín hiệu của thông điệp. a. Nếu thông điệp là phép kiểm tra điện kế thì nút sẽ gửi về nút di động rằng nó đang thực hiện kiểm tra. b. Tất cả các trường hợp khác đơn giản là phát quảng bá thông điệp để quảng bá đến các nút khác. Tuy nhiên trước khi phát quang bá nó xem ở trong bộ nhớ cache của nó xem có chắc chắn chưa gửi chưa. 2. Trạm cơ sở: Trạm cơ sở đợi thông điệp được gửi từ người dùng hoặc là nút định tuyến. Chương trình này thực hiện các nhiệm vụ từ thông điệp gửi đến. a. Nếu thông điệp là cổng nối tiếp thì ứng dụng cố gắng tìm ra vị trí của một nút. Khi đó trạm cơ sở sẽ gửi các tín hiệu quảng bá để nêu yêu cầu tìm ID của nút mà được gửi từ ứng dụng. b. Nếu thông điệp gửi đến là radio thì chỉ thị này chỉ ra các đáp ứng từ mạng mà nó yêu cầu. Thông điệp này chứa thông tin về vị trí của các nút đi động. Thông điệp này được chuyển đến người dùng thông qua cổng nối tiếp để xử lý và hiển thị. 3. Nút di động: Nút di động là một nút mà sẽ được tìm bởi hệ thống. Chương trình lắng nghe các thông điệp gửi đến. Khi thông điệp vị trí đến với một ID đích bằng với địa chỉ của chúng thì bắt đầu kiểm thử điện kế. Nó gửi đi thông điệp quảng bá với giá trị cao nhất điện kế. Đợi trong 3 giây đáp ứng từ các nút định tuyến .Bất cứ khi nào nhận được nút định tuyến. Bất cứ khi nào nhận Hoàng Anh Sơn – CT1002 43
  44. Đồ án tốt nghiệp đai học được nút định tuyến nó sẽ lưu ID của nút định tuyến và khoảng cách của nó vào trong một bảng. Tiếp tục kiểm tra cho đến chừng nào gặp những điều kiện sau. a. Nút di động nhận các đáp ứng từ 3 nút định tuyến láng giềng. b. Nút di động hoàn thành kiểm thử điện kế mà không cần nghe từ 3 nút. Trường hợp thứ hai nút di động đã ở ngoài khoảng hoặc nút di động đặt các gói tin gửi trở lại nút cơ sở thông qua nút định tuyến. 4. Bộ chuyển tiếp nối tiếp: Ứng dụng này là công cụ Java được đính kèm hệ điều hành TinyOS. Nhiệm vụ chính cung cấp đường liên kết giữa vị trí nút với cổng nối tiếp của máy tính. Công việc đi kèm với việc sử dụng soket TCP/IP với cổng 9000. Bất cứ chương trình nào muốn giao tiếp với mote đơn giản chỉ là đọc và viết thông điệp lên soket. Yêu cầu quảng bá: là chương trình liên kết giữa người dùng với chương trình chuyển tiếp serial forwarder. Chương trình hiển thị bản đồ nền nhà và các nút định tuyến. Giao điểm cho phép người dùng nhập ID của nút tìm kiếm. Chương trình lấy những giá trị này lắp ráp thành thông điệp chuyển tiếp lại trạm cơ sở thông qua trình serial forwarder. Khi mạng sensor tìm ra nút di động trạm cơ sở qua các thông tin vị trí trở lại thông tin quảng bá của chương trình yêu cầu. Chương trình hiển thị đồ thị những nút đã đáp ứng tới những nút di động và chỉ ra khoảng cách giữa nút di động với ba láng giềng gần nhất. 3.1.4 Kết quả đạt đƣợc Một thử nghiệm đã được thiết lập trong mạng cảm biến không dây ở trường Đại học Western Michigan[1]. Các chiều của phòng là 7m và 3m với diện tích là 21m2 . Các thử nghiệm ban đầu sử dụng 5 nút hạ tầng như minh họa trong hình 3.2 với 3*5 điểm được sử dụng cho các đối tượng được đặt. Các kết quả được hiển thị trong hình 3.6-3.9. Trong hình 3.6, tối thiểu, tối đa và các lỗi trong các kỹ thuật điện kế. Một đồ thị so sánh được thể hiện trong hình 3.7 cho các kỹ thuật RSSI. Hình 3.8 thể hiện sự biến thiên của hai kỹ thuật Hoàng Anh Sơn – CT1002 44
  45. Đồ án tốt nghiệp đai học bằng cách vẽ các độ lệch chuẩn của các lỗi. Thời gian trung bình để xác định vị trí cho mỗi kỹ thuật thể hiện trong hình 3.9. Hình 3.6: Kỹ thuật điện kế. Hình 3.7: Kỹ thuật RSSI Một cách để cải thiện cả về tính chính xác của hệ thống, cũng như thời gian để xác định vị trí, là tăng mật độ của các nút cố định. Thử nghiệm của kỹ thuật điện kế và kỹ thuật RSSI là chạy thử nghiệm hệ thống có thể được so sánh bằng cách sử dụng các nút cố định 5,7,9,11. Tăng mật độ của các nút cố định sẽ cải thiện tính chính xác của hệ thống, như minh họa trong cả hai hình 3.6 và hình 3.7. Tính chính xác của hệ thống RSSI tiếp tục cải tiến như là mật độ tăng, nhưng tính chính xác của kỹ thuật điện kế phụ thuộc số nút cố định . Bởi tăng số lượng các nút cố định thì chi phí tổng Hoàng Anh Sơn – CT1002 45
  46. Đồ án tốt nghiệp đai học thể của hệ thống tăng lên. Người sử dụng phải quyết định mức độ chính xác để xác định mật độ các nút cố định cho thích hợp. Hình 3.9 trong kỹ thuật điện kế thì khi giảm thời gian để định vị thì mật độ của các nút cố định tăng. Kể từ khi kỹ thuật RSSI luôn mất năm mẫu, thời gian để xác định vị trí bằng cách sử dụng hệ thống phụ này liên tục khoảng chín giây. Số lượng các nút định vị biến thiên trong cả hai kỹ thuật đòi hỏi mật độ cao. Hình 3.8 cho thấy độ lệch tiêu chuẩn của từng hệ thống giảm từ khoảng 20 inch với nút 5 đến khoảng 10 inch với các nút 11. Hinh 3.8 Tính biến thiên của hai kỹ thuật. Hoàng Anh Sơn – CT1002 46
  47. Đồ án tốt nghiệp đai học Hinh 3.9: thời gian định vị của hai kỹ thuật. Hệ thống Ferret là hệ thống định vi trong mạng không dây với chi phí thấp. Hệ thống này cho kết quả chính xác trong phạm vi 0.6 – 0.9m. Bảng dưới đây cho kết quả của một số hệ thống định vị. Hoàng Anh Sơn – CT1002 47
  48. Đồ án tốt nghiệp đai học Hệ thống Nơi phát triển Công nghệ Giải thích Beacon-based UCLA &USC 5 trạm radio Chính xác trong trong vùng vòng 1.83m trong 10*10m2 vòng 41.9s SpotOn Đại học Thẻ RSSI Độ chính xác phụ Washington thuộc vào các & Intel cluster Calamari Đại học Berkeley RSSI và TOF Kỹ thuật làm giải California sai sót Ferret Đại học Western Kỹ thuật điện kế Định vị trong vòng Michigan và RSSI 1m Bảng 3: Một số hệ thống định vị trong mạng sensor. Hệ thống Ferret định vị đối tượng trong phạm vi 1m vì vậy mà cần nhiều cải tiến để định vị được ở xa hơn. Thứ nhất các cảm biến Mica2 có chất lượng cao hơn so với radio. Thứ hai việc hiệu chuẩn hệ thống là quan trọng. Trong một môi trường dầy đặc thì việc kiểm soát môi trường, hiệu chuẩn một cách tự động. Một chiến lược hiệu chuẩn mà có thể được sử dụng trong thực tế là sử dụng các nút được biết đến. Khi hiệu chuẩn là cần thiết, các các nút được các láng giềng trao đổi các thông điệp và kiểm tra các giá trị RSSI. Giá trị này cho thấy mức độ ổn định của môi trường. Hoàng Anh Sơn – CT1002 48
  49. Đồ án tốt nghiệp đai học 3.2 Định vị toàn mạng Trong phần trên chúng ta đã trình bày phương pháp xác định vị trí của một đối tương. Bây giờ chúng ta sẽ trình bày phương pháp xác định vị trí của tất cả các nút trong mạng cảm biến không dây. Trong chương I chúng ta đã thảo luận về tầm quan trọng của vấn đề này. Trong thực tế thì không thể trang bị cho tất cả các nút cảm biến hệ thống GPS. Một số phương pháp tiếp cận được sử dụng là tính toán lặp đi lặp lại để cho vị trí của các nút trong mạng cảm biến. Việc tính toán lặp đi lặp lại gây ra lãng phí năng lượng mà vấn đề năng lượng là vấn đề cốt lõi của hệ thống mạng sensor. Vì vậy mà chúng tôi sẽ trình bày về cách xác định vị trí của các nút trong mạng cảm biến mà sử dụng năng lượng một cách hiệu quả. Mục đích là tìm ra vị trí của các nút trong mạng mà cho trước một tập con các nút. Chúng tôi tìm ra những phương pháp tối ưu lặp không phù hợp cho thực tế phân tán của toàn mạng. Đôi khi thì một ứng dụng thường được phù hợp cho dữ liệu đẩy về nút cơ sở. Điều này cho kết quả là năng lượng được cải thiện và tăng độ chính xác. Kỹ thuật trong phần này được trình bày là chiến lược tiến hóa. Nó độc lập với phương pháp phân khoảng. Thường sử dụng ước lượng để tính khoảng cách giữa các nút và nút cơ sở. Liên quan đến việc tính toán phương pháp đề xuât cung cấp việc tiết kiệm năng lượng đáng kể hơn so với các phương pháp khác bằng việc so sánh và yêu cầu một láng giềng cho mỗi nút cảm nhận thay vì ba nút giềng như các kỹ thuật khác. Bởi vì việc tiêu thụ năng lượng lớn lên chúng tôi đưa ra các phương pháp tối ưu lặp. Nó không phải là luôn luôn phù hợp với các mạng phân tán trong thực tế. Những kỹ thuật này phù hợp hơn với việc thực hiện kiểu chủ tớ (nút sink làm chủ) và thực hiện một lượng lớn trong tính toán. Phần này chúng tôi sẽ trình bày phương pháp sử dụng năng lượng một cách hiệu quả để xác định vị trí các nút trong mạng có biết trươc một số nút. Việc sử dụng chiến lược tiến hóa độc lập với phương pháp ước lượng khoảng cách giữa các nút với các nút cơ sở. Hoàng Anh Sơn – CT1002 49
  50. Đồ án tốt nghiệp đai học Trong các chương trình trước chúng tôi phát triển hệ thống Ferret[1] sử dụng sóng radio để xác định vị trí của đối tượng trong vòng 1m. Hệ thống sử dụng các nút cố định để xác định vị trí. Chúng tôi sẽ tìm hiểu về LESS (Localization Using Evolution Strategies in Sensornets), trong đó việc ươc lượng các vị trí trong mạng có biết trước một số nút. Những đặc tính tương tự được đề xuất trong hệ LESS khi chúng tôi so sánh bao gồm: 1. Chỉ cần duy nhất một nút láng giềng cho một nút mạng cảm biến thay vì ba nút láng giềng như trong các kỹ thuật khác. 2. Tiêu thụ năng lượng ít. 3. Kỹ thuật tối ưu hóa năng lượng dựa vào chiến lược tiến hóa. 4. Các nút cơ sở tham gia vào việc tính toán. Vì bài toán xác định vị tri là bài toán NP-khó. Kỹ thuật heuricstic phải được sử dụng để giải bài toán trong thời gian đa thức. Đó là thách thức cần phải được giải quyết trong thực tế đó là khoảng cách không chính xác giữa các cặp nút. Thay vào việc ước tính thì ta sẽ sử dụng xấp xỉ để tính khoảng cách. Chiến lược tiến hóa là một kỹ thuật được sử dụng thành công trong một số bài toán khó và là phương pháp được sử dụng trong hệ LESS. Hệ thống LESS Chiến lược tiến hóa dựa trên nguyên tắc lựa chọn các hiệu chỉnh trong thời gian tự nhiên. Mỗi thế hệ (sự lặp lại của thuật toán) phải mất tiềm năng phát tán thực hiện biến đổi di truyền để biến đổi vật liệu di truyền(các tham số di truyền) để tạo ra một thế hệ mới, cả cha và con được ước tính nhưng duy nhất các cá thể có sự phù hợp thì sẽ tồn tại và phát triển[4]. Cho (µ + ) và (µ, ) là phiên bản của chiến lược tiến hóa. µ là cha tạo ra, là con. Sử dụng cơ chế kết hợp and/or. Mặc dù trong (µ, ) thì phiên bản tốt hơn phiên bản µ. Đó là sự khác biệt của phương pháp lựa chọn này. Sự khác nhau của phương pháp lựa chọn này là trong (µ + ) phiên bản, µ là các cá nhân Hoàng Anh Sơn – CT1002 50
  51. Đồ án tốt nghiệp đai học được tạo ra từ cha mẹ và các con mồ côi tạo thàh một cộng đồng thế hệ tiếp theo. Mặt khác trong các phiên bản (µ, ) thì µ là cá thể tốt nhất được lựa chọn ( > µ) thế hệ con. Chúng tôi phát triển hệ thống LESS dựa trên chiến lược tiến hóa. Dựa vào kết quả thực hiện chúng tôi quyết định phát triển hệ thống LESS dựa vào sử dụng (µ + ) chiến lược tiến hóa. LESS được ước lượng tất cả các nút trong mạng cho một vị trí một nhóm nhỏ các nút. Nó ước lượng bằng việc sử dụng vị trí của một số nút đã biết. Mặc dù kỹ thuật phân khoảng đã tạo ra một số các lỗi định vị nhỏ hơn nhưng LESS không phát triển trên kỹ thuật phân khoảng. Hệ thống giả định một tập con các nút neo nhận thức được vị trí của chúng. Nút neo được đặt vào vị trí đã biết hoặc là được trang bị GPS. Đơn giản là hệ thống giả định rằng các tín hiệu là thẳng hướng từ hệ thống. Tất cả các nút đều có phạm vi truyền như nhau. Mỗi nút có ít nhất một láng giềng. Một số các kỹ thuật định vị trước gặp thất bại khi mà nút đó không có ít nhất là ba láng giềng trở lên. Từng cá thể trong mỗi thế hệ trong chiến lược tiến hóa được giải quyết tính phù hợp nhất trong mỗi cá thể. Các cá thể phù hợp nhất sẽ được trình bày lại bằng việc gắn định vị trong đó các cặp được đặt mà khoảng cách được đặt gần với phương pháp ước tính khoanh vùng của chúng. Các cá thể phù hợp được tính toán bằng việc tìm ra sự khác nhau giữa các cặp vị trí, các nút và các ước lượng vùng. Sau đó tính tổng hình vuông của sự khác biệt này(Hình 3.10 và phương trình 1). Đặc biệt với giải thuật tiến hóa thì nó sẽ kết thúc khi: 1. Các thế hệ là cố định. 2. Mức cá thể phù hợp. 3. Chiến lược tiến hóa không có sự cải thiện. LESS thực hiện nhƣ sau: Hoàng Anh Sơn – CT1002 51
  52. Đồ án tốt nghiệp đai học 1. Mỗi nút sử dụng kỹ thuật phân khoảng (ranging ) để ước lượng khoảng cách chính nút đó tới các láng giềng. Các cặp khoảng cách láng giềng này được chuyển tiếp đến nút cơ sở. Giả sử rằng nút có sở không phải là nút cảm nhận mà là một thiết bị có năng lực tính toán mạnh ví dụ như máy tính. Thiết bị này khác nút cảm nhận. 2. Khởi tạo một quần thể gồm µ cá thể bằng việc lựa chọn cho mỗi N nút trong mạng được lựa chon. Các nút neo có thể được đặt trong vị trí chính xác. Các nút láng giềng của nút neo được đặt kế bên. Các nút khác không phải là láng giềng của nút neo thì được đặt ngẫu nhiên. 3. Mỗi cá thể, thế hệ con được áp dụng thuật toán trộn (đột biến). 4. Việc lượng hóa tất cả các cá thể được tính lượng phù hợp của chúng. Hàm phù hợp được giả sử là một hình vuông giữa vị trí nút và ước lượng khoảng( công thức 1). 5. Chọn những cá thể phù hợp thì sống sót các cá thể còn lại thì loại bỏ. 6. Lặp lại bước ba cho đến khi điều kiện không phù hợp(ba điều kiện không thỏa mãn thì dừng). Phép đột biến được thực hiện bởi ứng dụng ngẫu nhiên với bốn toán tử sau. a. Chọn ngẫu nhiên một nút mà không phải nút neo và di chuyển chúng theo hướng trục X một khoảng Δx. b. Chọn ngẫu nhiên một nút mà không phải nút neo và di chuyển chúng theo hướng trục Y một khoảng Δy. c. Chọn ngẫu nhiên hai nút không phải là nút neo và trao đổi tọa độ x. d. Chọn ngẫu nhiên hai nút không phải là nút neo và trao đổi tọa độ y. Hoàng Anh Sơn – CT1002 52
  53. Đồ án tốt nghiệp đai học Hình 3.10: Lỗi định vị trong phép đột biến. Hình 3.10 minh họa hoạt động đột biến cải thiện tính phù hợp để cải thiện trong hệ thống LESS. Hình 3.10a, Xa là vị trí chính xác của nút láng giềng N1, N2, N3 với khoảng cách chính xác giữa X và các láng giềng được liệt kê là a1, a2, a3 Hình 3.10a, Xe là vị trí ước lượng bằng một cá thể trong giải thuật bằng một cá thể trong giải thuật tiến hóa. Ước lượng này sẽ dẫn tới khoảng cách láng giềng là d1, d2, d3. Vì chúng ta biết được khoảng cách tới nút láng giềng thì lỗi liên quan đến nút láng giềng được tính theo công thức: 3 2 Error = (di ai ) (1) i 1 Hoàng Anh Sơn – CT1002 53
  54. Đồ án tốt nghiệp đai học Có thể được tính toán bằng việc tính tổng của n nút trong mạng cảm nhận bốn toán tử giao hợp nêu trên. Giả sử cái thứ nhất được lựa chọn điều này có thể di chuyển đến vị trí ước lượng là Δx theo trục x (hinh 3.10b). Toán tử đột biến di chuyển vị trí ước tính Xe gần vị trí chính xác bằng việc thay thế tọa độ x của chúng với khoảng cách ước lượng mới gần hơn khoảng cách chính xác thì lỗi theo công thức 1 sẽ là nhỏ hơn. Điều này làm tăng khả năng phù hợp của tiềm năng phép giải mã trong đó cải thiện cơ hội sự sống sót của thế hệ kế tiếp. 3.3 Thuật toán xác định vị trí Một số thực nghiệm về lược đồ trọng số không cân bằng.Trong mô phỏng các cụm láng giềng được xây dựng bằng các nút hình cây. Sau đó phần mền được thực hiện trên mỗi vị trí P của lưới. Đối với mỗi vị trí P giả lệnh tính toán giữa các lược đồ trọng số không cân bằng và lược đồ trọng số cân bằng. Trong trường hợp đặc biệt ước lượng trọng số chứa các lỗi gây ra bởi lược đồ trọng số không cân bằng trong khi biến ước lượng không chính xác chứa lỗi biến trung bình trọng số cân bằng. Các giá trị lỗi đều có trạng thái là khoảng cách trung gian giữa vị trí chính xác P và vị trí tính toán. Sự khác biệt là 0 nếu khoảng cách không gian giữa vị trí thực và vị trí tính toán. Bất cứ một giá trị vị trí đều phản ánh vector khoảng cách giữa P và vector vị trí giả định. Phương pháp được đề xuất khi vị trí tính toán của nó gắn với vị trí thực của P so với đề án trọng số bằng nhau. Hình 3.11 cho thấy một biểu đồ sự cải thiện của vị trí được trả về qua hàm chức năng: FLOAT improvement(position P, nodes[k] N) // calculate distances to all spanning nodes FOR EACH of the k nodes N[i] spanning the patch BEGIN Hoàng Anh Sơn – CT1002 54
  55. Đồ án tốt nghiệp đai học dist_PN[i] = distance(P,N[i]) // and disturb by certain error dist_PN[i] += error(dist_PN[i]) END // each triple (i,i+1,i+2) of nodes // creates a position estimate FOR EACH of the k nodes N[i] spanning the patch position_suggestion[i] = triangulate(dist_PN[i],dist_PN[(i+1) MOD k],dist_PN[(i+2) MOD k] // the final position is a weighted sum // of the position estimates estimation_weighted = estimation_trivial = 0 FOR EACH of the k nodes N[i] spanning the patch BEGIN estimation_weighted += position_suggestion[i]*weight[i] estimation_trivial += position_suggestion[i]/k END improvement = ABS(P-estimation_trivial) - ABS(P-estimation_weighted) return improvement Nếu khoảng cách distP,N là chính xác thì chính xác của vị trí P trở lên hoàn hảo. Tuy nhiên trong thực tế thì khoảng cách chỉ có thể được dự đoán. Hoàng Anh Sơn – CT1002 55
  56. Đồ án tốt nghiệp đai học Trong hình 3.11 việc đạt được độ chính xác trung bình trong đề án trọng số không cân bằng cho topo được hiển thị bởi bởi 6 nút. Những điểm tối màu là điểm mà độ chính xác được cải tiến. Những cải tiến được thực hiện tại những cạnh và đỉnh của vùng. Sự cải thiện hướng về trung tâm của trọng lực. Vì các trọng số ngày càng trở lên cân bằng vì thế việc hội tụ sẽ chống lại trọng số. 3.4 Kết luận Trong mạng WSN việc xác định vị trí của các nút trong mạng là rất cần thiết. Trong chương 3 này chúng ta đã đi tìm hiểu về một số các kỹ thuật định vị bằng điện kế, kĩ thuật RSSI và sử dụng chiến lược tiến hóa để xác định vị trí của các nút trong mạng thông qua tìm hiểu hai hai hệ thống Ferret và hệ thống LESS. Hoàng Anh Sơn – CT1002 56
  57. Đồ án tốt nghiệp đai học CHƢƠNG 4: GIẢI MỘT SỐ BÀI TOÁN ĐỊNH VỊ HÌNH HỌC Để hiểu rõ hơn về việc định vị nút mạng ta sẽ đi tìm hiểu thực tế bằng cách nghiên cứu một số bài toán khác nhau để thấy được cách xác định vị trí của nút mạng trong mạng cảm biến không dây WSN. 4.1 Định vị không ƣớc lƣợng khoảng cách. Bài toán: Cho hai nút A và B không biết được vị trí của chúng nhưng có thể nghe được nhau. Nút A có các láng giềng (1,5) và (3,4) và B có các láng giềng (0.5,2) và (2,1.5). Miền vòng tròn radio của của các nút đều phủ được 1.5 đơn vị.Hỏi: a. Vị trí của nút A có thể là (2,4) hoặc (2,5) b. Thiết lập vị trí nút C và biết vị trí một cặp láng giềng. Khoảng cách giữa các nút không được ước tính nhưng vị trí của C có thể được ước lượng(trong miền sóng tới). Miền sóng radio của tất cả các nút đều biết. Hỏi: i. Giới hạn trên cho lỗi giữa vị trí nút ước lượng và vị trí nút thực tế là bao nhiêu? Đặt vị trí nút ở đâu thì có lỗi lớn nhất. ii. Có thể cấu hình các nút mà lỗi trong đó của các nút là bằng không. Bài giải: a> Một số giải pháp được đề ra là định vị đơn toàn cầu “Localization Simple global positioning”. – Nút B có được vị trí trong khu vực của nó ( màu xám như trong hình) để nó có thể tạo ra vùng rộng lớn nhất cho nút A. Nói cách khác không có sự định vị tự do cho nút A. Vì vậy mà nút B được di chuyển đến vị trí n. – Việc tính toán vị trí n trở lên dễ dàng do các vòng tròn đều có cùng một bán kính. Đó là vì sao mà điểm s nằm ở giữa hàng xóm của nút B. Đường Hoàng Anh Sơn – CT1002 57
  58. Đồ án tốt nghiệp đai học vuông góc giữa các nút hàng xóm đã dẫn đến vị trí n. Khoảng cách từ s đến n được xác định bằng định lý Pitago. Vị trí (2,4) trong phạm vi của n vì |(2,4) - n|=~1.1. Vị trí (2,5) là ngoài vùng của n vì |(2,5) - n|=~2.1. Vì vậy giá trị (2,5) không hợp lệ cho vị trí A. b> Chúng ta sẽ đưa ra giải pháp cho phần b. i: Các ràng buộc trên đối với các lỗi khi dự đoán vị trí của một nút không bao giờ có thể được lớn hơn phạm vi nhỏ nhất của tất cả các trạm phát radio hàng xóm. Hình dưới là ký họa một kịch bản với một người hàng xóm. Trong Hoàng Anh Sơn – CT1002 58
  59. Đồ án tốt nghiệp đai học trường hợp xấu nhất các nút ở biên giới của các nươc láng giềng không được định vị. Nếu sai vị trí thì các hàng xóm sẽ không biết được vị trí của nó nữa. Mỗi nút sẽ không bao giờ mở rộng thêm lỗi này nhưng nó có thể sẽ làm giảm diện tích hợp lệ của nút khi không có vị trí như thể hiện trong các ký họa dưới đây. Chú thích: + Đúng, nhưng không rõ vị trí của nút không định vị × Vị trí của láng giềng Dự đoán vị trí của nút không định vị ii:Lỗi giữa vị trí giả định và vị trí thực có thể là không nếu nút đó có thể nghe hàng xóm của nó như tại vị trí của nó. 4.2 Xác định vị trí tƣơng đối bằng ƣớc lƣợng khoảng cách Bài toán: Chọn nút i ở trung tâm của hệ trục tọa độ của toàn mạng. Nút k cũng được bản địa hóa làm láng giềng của nút i. Mỗi nút được thêm vào biết vị trí của nút k nhưng không biết vị trí của nút i. a. Tại sao các nút láng giềng của k phải được biến đổi để phù hợp với cơ sở toàn cầu. Liệu có dễ dàng tính toán hơn nếu nút k được đặt trên hệ tọa độ y không. b. Hãy vẽ cấu hình các nút trong đó láng giềng của k phải di chuyển nhưng không quay trong hệ trục tọa độ. c. Hãy tìm trường hợp mà k có thể xoay nhưng không dịch chuyển. d. Hãy tìm một trường hợp mà phép quay phép dịch và phép lấy đối xứng là cần thiết. Hoàng Anh Sơn – CT1002 59
  60. Đồ án tốt nghiệp đai học Bài giải: a. Đầu tiên mỗi nút định nghĩa vị trí của mình như là trung tâm. Tại thời điểm này chỉ biết đến người hàng xóm. Nút không có ý tưởng gì về “ở trên”, “dưới”, “trái”, “phải” (hoặc là bắc, nam, đông, tây). Nó có thể được định nghĩa một cách tùy ý. Sau đó nó sẽ được chọn ngẫu nhiên bởi các nút ở trung tâm và tất cả các nút khác sẽ phải thích ứng với định nghĩa này. Biểu thức của hệ trục tọa độ có thể được chọn duy nhất hoặc một vài tham chiếu toàn cục khác. b. Các nút A và B được định nghĩa đối với nút k. Trục của k đều cùng hướng như các trục của cơ sở toàn cầu của nút i nên chỉ dịch là được. c. Việc dịch vị trí là không cần thiết khi mà nút i và k cùng vị trí. Trên lý thuyết điều này khó có thể xẩy ra nhưng có thể xẩy ra trong thực tế do việc ước lượng khoảng cách không chính xác. e. Hình dưới đây là một hình minh họa một trường hợp mà phép quay phép dịch và phép lấy đối xứng là cần thiết cho việc định vị. Hoàng Anh Sơn – CT1002 60
  61. Đồ án tốt nghiệp đai học 4.3 Xác định trục tọa độ thông qua khoảng cách Bài toán: Cho các nút A-G có các khoảng cách được cho dưới bảng sau. A B C D E F G A 0 2.24 3.16 1.41 2.24 B 2 C 0 1.41 1 2.24 1.41 D 2.24 2 1.41 0 2.24 2.24 2 E 3.16 1 2.24 0 2 1 F 1.41 2.24 2.24 2 0 1 G 2.24 1.41 2 1 1 0 Hoàng Anh Sơn – CT1002 61
  62. Đồ án tốt nghiệp đai học Trong bảng các ô trống thì biểu thị là không có kết nối giữa các nút đang tồn tại. a. Nút nào là nút phù hợp với với trục tọa độ toàn cục và đối với trục X. Nút nào là nút ít phù hợp nhất? Tại sao? b. Nút C được định nghĩa là trục tọa độ cục bộ hãy chọn nút E trên trục X và nút G trên trục Y hãy xác định trục tọa độ toàn cục tại vị trí (1,1) đuợc định nghĩa cho nút C. c. Vấn đề nào xẩy ra khi định vị nút B một nút , một nút có thể được tìm dưới các điều kiện hạn chế? Hãy mô tả quá trình và tọa độ. Bài giải: a.Nút D được chọn vì nó có thể nghe được các nút khác resp, nó ước lượng khoảng cách tới tất cả các khác. G hoặc F có thể được sử dụng như x-trục vì họ được kết nối với tất cả các nút khác trừ B. Đối với các giải pháp sau đây chúng ta định nghĩa: D: làgốc G: xác định các trục x F: xác định hướng của trục y Node B là các nút ít nhất là phù hợp để xác định nguồn gốc bởi vì D chỉ có thể nghe và ước tính khoảng cách tới B. Không có nút khác có thể định vị nhờ sự trợ giúp của nút B. b. Ta sẽ đưa ra giải pháp tiến hành giải phần b. Các cơ sở (phối hợp hệ thống) của D: Ban đầu chúng tôi chỉ xác định được nguồn gốc của nút D và G được xác định là trên trục x. Khoảng cách từ D đến G là 2 theo bảng tọa độ của G là (2,0). Bây giờ ta sẽ tính tọa độ của F. Theo hàm cos của góc gamma giữa DG và DF được xác định như sau. Hoàng Anh Sơn – CT1002 62
  63. Đồ án tốt nghiệp đai học Các nhân tố để xác định điểm F được lấy từ bảng (khoảng cách DF) với việc quyết định tính sin(gama), chúng tôi xác định điểm F nằm trên trục x. Chú ý rằng sin(-gama) = -1 cũng là một lựa chọn hợp lệ Các cơ sở của nút C: Chúng tôi chọn nút cơ sở là nút D và giải pháp được đưa ra là nút C. Khi chọn C thì sẽ sử dụng nút E làm trục x và chon nút G làm trục y. Chúng tôi thực hiện việc lặp đi lặp lại việc tính toán như viêc thực hiện với nút D. Hệ tọa đọ E cho vị trí E(0,1) cho khoảng cách từ C đến E là 1 theo bảng. Chúng ta sẽ phải tính toán vị trí của G. Bây giờ nút cơ sở C sẽ được xoay để liên kết với nút D. Rõ ràng việc biết các nút C, E và G là hạn chế đối với nút D. Đầu tiên ta sẽ xem xét nút C. Hoàng Anh Sơn – CT1002 63
  64. Đồ án tốt nghiệp đai học Góc giữa trục x của D và đường thẳng DC là: Chú ý rằng có các trường hợp khác xuất hiện ở đây bởi vì góc giữa D trên trục x và đường DC có thể vẽ đường phía trên hoặc phía dưới của trục x. Nó đã không xẩy ra chon đến nay bởi vì chúng tôi đặt trục y một điểm tự do trên hướng nhất định nào đó. Cả hai trường hợp (cho C ở trên hoặc dưới) có thể phân biệt dễ dàng nếu khoảng cách tới nút F được tính. Đối với điểm (1,1) thì khoảng cách là 1 tuy nhiên theo bảng thì điều này chỉ đúng cho điểm C(1,-1). Cũng tương tự như hệ trục tọa độ của nút E trong hệ cơ sở của D. Nút G được biết đến trong việc tính toán trước. Hoàng Anh Sơn – CT1002 64
  65. Đồ án tốt nghiệp đai học Theo bảng thì khoảng cách EF là 2. Theo đó tọa độ của E(2,-1). Tại thời điểm này gần như các tác vụ được thực hiện vì các trục của D là song song với các trục của C. Vì vậy mà điểm C (1,1) được chuyển đổi thành vector (1,-1). Hay nói cách khác cơ sở của C khác với cơ sở của D trong trường hợp này. Giải pháp cho điểm chuyển đổi này là (2,0). Nếu các trục tọa độ của C và D là không song song thì ta sẽ thực hiện phép xoay hệ trục tọa độ. Trong trường hợp đặc biệt phép xoay là không cần thiết vì 1350 + 450 +1800 = 00. Đối với các trường hợp khác thì ta sẽ tiến hành quay trước khi chuyển đổi. Hoàng Anh Sơn – CT1002 65
  66. Đồ án tốt nghiệp đai học c> Khi nút C có duy nhất một hàng xóm trong một vùng hợp lệ thì vị trí của nó có thể bị giới hạn bởi một số các mức độ nhất định. Theo bảng thì khoảng cách BD được biết đến vì vậy mà B nằm trên đường tròn xoay quanh D với bán kính là DB. Đồng thời trong thời gian nay thì nút B không nghe được nút A và C nên vùng này có thể được loại trừ khỏi vòng tròn. 4.4 Kết luận Trong chương này chúng ta đã đi nghiên cứu một số các bài toán định vị. Qua đó ta đã thấy được quá trình tiến hành xác định vị trí của nút mạng. Từ đó ta có thể thấy được sự quan trọng của việc định vị nút mạng trong hệ thống mạng cảm biến. Hoàng Anh Sơn – CT1002 66
  67. Đồ án tốt nghiệp đai học KẾT LUÂN Các khái niệm và các vấn đền liên quan đến mạng cảm biến vấn còn là vấn đề khá mới mẻ với nhiều người. Trong đồ án này em đã trình bày tổng quan về mạng cảm biến. Với các tính năng ưu việt cùng với các ứng dụng đa dạng nó có thể làm việc trong các điều kiện khắc nhiệt mà không phải mạng nào cũng có. Vì vậy mà trong tương lai không xa thì mạng cảm biến sẽ phát triển nhanh chóng. Em hy vọng rằng đồ án này sẽ đóng góp một phần nhỏ vào việc nghiên cứu về lĩnh vục còn tương đối mới mẻ ở Việt Nam. Trong phạm vi của đồ án này em đã nghiên cứu được khái quát về mạng cảm biến và tìm hiểu về nguyên lý định vị các phương pháp định vị và giải thuật định vị nút mạng. Và đã biết được cách xác định vị trí nút mạng và biết được cách tính toán xác định vị trí của nút mạng thông qua một số các bài toán. Do đây là vấn đề mới mẻ cùng với kiến thức còn hạn chế và thời gian nghiên ngắn lên đồ án của em không tránh khỏi những thiếu sót, em rất mong nhận được sự phê bình, của các thầy cô để đồ án của em được hoàn thiện hơn. Một lần nữa em xin cám ơn PGS.TS Vương Đạo Vy , Khoa Điện Tử Viễn Thông. ĐHCN, ĐHQGHN cùng với thầy giáo Ths Nguyễn Trọng Thể, Khoa Công Nghệ Thông Tin DHDL Hải Phòng đã nhiệt tình giúp đỡ em trong thời gian vừa qua. Hải Phòng, Tháng 7 năm 2010 Sinh viên thực hiện Hoàng Anh Sơn Hoàng Anh Sơn – CT1002 67
  68. Đồ án tốt nghiệp đai học TÀI LIỆU THAM KHẢO [1] Mark Terwilliger, Ajay Gupta, Vijay Bhuse, Zille Huma Kamal, and Mohammad Ali Salahuddin, "A Localization System using Wireless Network Sensors: A Comparison of Two Techniques", The Proceedings of the First Workshop on Positioning, Navigation and Communication, Hannover, Germany, March 2004. [2] J. Hill, R.Szewczyk, A.Woo, S. Hollar, D. Culler, and K. Pister, “System Architecture Directions for Networked Sensors,” Proceedings of the 9th International Conference on Architectural Support for rogramming Languages and Operating Systems, November 2000. [3] Mark Terwilliger, Ph.D. Western Michigan University, 2006 [4] D. Fogel, Evolution Computation, IEEE Press, 1995. [5] Sensor Networks Thomas Haenselmann September 29, 2008 [6] Networking Wireless Sensor, Bhaskar Krishnamachari, Cambridge University Press 2005 [7] Jeffrey Hightower, Gaetano Borriello, Location Systems for Ubiquitous omputing, IEEE Computer, August 2001. Hoàng Anh Sơn – CT1002 68