Luận văn Nghiên cứu mạng Camera thông minh phục vụ giám sát an ninh

tác tử SmartCam quản lý việc triển khai các nhiệm vụ giám sát trong hệ thống, bao gồm cả mã quản lý tác tử SmartCam; tải mã nhị 30 Mobile-Agent là một phần mềm (chương trình) tồn tại trong một môi trường nhất định, có khả năng thay đổi vị trí, tự động hành động phản ứng lại sự thay đổi của môi trường nhằm đáp ứng mục tiêu đã được thiết kế trước. Tác tử có các tính chất chung như: tự động, bền bỉ, phản ứng tức thì, hướng mục tiêu, khả năng giao tiếp với tác tử khác hoặc con người. 31 Decentralized Information Ecosystem Technologies 85 phân cho DSP; đề xuất các mức QoS ứng dụng cũng như tính toán chi phí cho mỗi nhiệm vụ giám sát. Do đặc tính di động nên tác tử DSP phải có khả năng di dời giữa các host. Trong trường hợp có dịch chuyển thì tác tử DSP sẽ tạm dừng xử lý tính toán của DSP này, chuyển trạng thái và tái hoạt động phía bên kia. Theo phần việc đảm nhận mà các tác tử DSP hoạt động ở các chế độ như: - Node Information Agent (NIA) làm nhiệm vụ truyền thông tin về nút, SC cho các nút, SC khác. NIA được sử dụng trong quá trình khởi tạo hoặc hiệu chỉnh s_clu để cung cấp thông tin cho các SC thành viên và nghe ngóng dịch vụ của các tác tử khác. - Cluster Manager Agent & Proxy (CMA CMP) điều khiển các SC thành viên trong s_clu. CMA được liên kết đến mọi SC trong s_clu tuy nhiên nó chỉ truyền thông tương tác đến CMP. CMP cũng liên kết đến mọi SC trong s_clu và chỉ chuyển tiếp thông tin điều khiển hoặc hàng đợi đến CMA, nơi mà phần lớn các lệnh điều khiển liên quan đến bổ sung hay gỡ bỏ SC trong nhóm. Cấu trúc CMA/CMP là trong suốt đối với người dùng và các điều khiển vận hành hay hàng đợi luôn được hướng tới NIA. - DSP Interaction Agent (DIA) nhằm tích hợp các DSP trong hệ thống. DIA đơn giản ghép nối các DSP-lib, cung cấp các chức năng tải mã nhị phân xuống DSP và quản lý các mã đó. Hơn thế DIA còn xuất trình và đăng ký dịch vụ cho hệ truyền thông điệp giữa các DSP. Ứng dụng trong DSCP Quá trình phân bổ nhiệm vụ giám sát được bắt đầu dựa vào sự kiện phần cứng hoặc phần mềm xảy ra, trong trường hợp có SC thành viên trong s_clu bị thay đổi hoặc khi có s_clu mới được tạo lập. 86 Khi đó SC nắm bắt được sự kiện sẽ chủ trì việc phân bổ gọi là initiator thông qua các thủ tục liên kết. Hành động đầu tiên là kiểm tra các SC khác xem chúng đã đang được phân chia nhiệm vụ hiện thời như thế nào. Initiator tạo các tác tử công việc32 trong mọi SC trong s_clu. Những tác tử công việc này bao gồm danh sách các nhiệm vụ giám sát được gán cho s_clu, mức QoS của chúng và các yêu cầu ràng buộc. Các tác tử công việc lập thành hàng đợi cho DIA nhằm phát hiện số lượng và tải hiện thời của các DSP trong SC. Dựa trên những hiểu biết này, mọi tác tử công việc giải quyết vấn đề CSP cục bộ và thông báo về SC initiator, đến đây là hoàn thành phần việc cục bộ. Nhằm hợp nhất các liên kết thành phần, initiator tạo nhóm hợp nhất các SC hoặc các tác tử công việc trong đó. Một tác tử công việc trong nhóm được coi là master trong khi cái còn lại được coi là slave của quá trình hợp nhất. Sau khi initiator đã tạo được các nhóm hợp nhất thì các tác tử slave di trú sang tác tử master, nơi mà chúng hợp nhất các liên kết thành phần. Khi quá trình hợp nhất kết thúc master thông báo điều này đến initiator. Tác tử slave tạm dừng tại đây. Initiator lại tiếp tục tạo các nhóm hợp nhất khác và khởi tạo quá trình kết hợp. Những bước này được thực hiện cho đến khi mọi liên kết thành phần được kết hợp toàn bộ. Nhằm đảm bảo cho kết quả của phép hợp nhất được lưu giữ tại Initiator SC thì initiator luôn là tác tử master trong các thủ tục hợp nhất mà có sự tham gia của nó. Cuối cùng, tác tử master trong Initiator SC đưa ra danh sách cuối cùng của các liên kết, đã được kiểm tra về tính toàn vẹn vì việc trộn không đảm bảo mọi phương án phù hợp với mọi nhiệm vụ. Trong trường hợp không tìm 32 Load Distribution Worker agent LDW 87 ra liên kết trọn vẹn thì tác tử master thông báo liên kết gần toàn vẹn nhất cho initiator. Tác tử master tạm dừng ở đây. Initiator cuối cùng quyết định chọn hướng liên kết có giá thấp nhất và bắt đầu triển khai. Khi đó initiator mới thông báo đến các tác tử DSP để chúng thay đổi liên kết. Các tác tử có thay đổi mức QoS thì chỉ cần đổi mức xử lý trong khi các tác tử khác có thể phải di trú sang SC mới. Vào thời điểm này initiator quảng bá phương án được chọn cho mọi SC trong s_clu và trả quyền điều khiển cho SC. Tái sử dụng các liên kết Nhằm mục đích sử dụng lại các phương án liên kết không còn hữu dụng thì những phương án này thay vì bị loại bỏ thì được đánh dấu 'loại', ghi chú rõ nguyên nhân tại sao loại và lưu lại. Khi đó thì trong trường hợp hệ thống được giảm tải thì có khả năng sẽ dùng lại được những phương án đã bị loại đó. Trong các nhiệm vụ cụ thể sẽ có khả năng xuất hiện tác tử chỉ tồn tại trong một khoảng thời gian ngắn. Ví dụ như trong bài toán theo vết đối tượng trong thị trường giám sát thì tác tử lần vết này chỉ tồn tại trong một thời gian ngắn tại SC nên các tác tử loại này được gọi là transient agent. Bài toán ví dụ về theo vết đối tượng là người trong thị trường giám sát Khi có đối tượng di chuyển trong thị trường quan sát của SCA thì các thông tin lưu vết ví dụ như color histogram sẽ được sử dụng để tách biệt miền chuyển động, làm mịn khối và nhận dạng người theo tỷ lệ đầu/thân. Khi này SCA được coi là initiator. Với việc dự đoán hướng chuyển động của đối tượng thì SCA sẽ tạo ra các tác tử công việc cho các SC trong s_clu tại góc hướng đó là các nhiệm vụ giám sát như tính toán tốc độ di chuyển, loại hình chuyển động, chụp hình, quay đoạn hình, bắt tiêu điểm vào vùng đầu mặt... QoS của 88 các nhiệm vụ này được sử dụng là QoS chung tuy nhiên mức QoS có thể được nâng lên nếu giá trị đặc trưng tính toán bị vượt ngưỡng33 cho phép. Các nhiệm vụ giám sát trên lập thành hàng đợi cho DIA để xác định số lượng và tải hiện thời của các DSP trong các SC trong s_clu được dự đoán là sẽ có đối tượng di chuyển đến. Bản thân các SC này có thể cũng đang thực thi các nhiệm vụ giám sát khác hoặc đang ở chế độ tiết kiệm năng lượng. Do vậy không phải là nhiệm vụ sẽ được gán cho tất cả các SC. Những tính toán cục bộ tại các SC này sẽ được thông báo về initiator SCA. Chuyển sang giai đoạn hợp nhất các liên kết thành phần, dĩ nhiên tại thời điểm này initiator SCA vẫn là master. Trong trường hợp không có liên kết đảm bảo QoS chung thì các tác động có thể của master là kích hoạt các SC đang hoạt động ở mức tiết kiêm năng lượng hoặc giảm tải34 tại các SC trong s_clu. Cuối cùng, khi đối tượng đã di chuyển ra khỏi thị trường quan sát của SCA thì tác tử master này được chấm dứt khi có thông báo phản hồi từ các tác tử slave là đã có đối tượng trong thị trường quan sát. Các thông số trạng thái của tác tử này đã được di trú sang tác tử tại SC khác. SC này được coi là initiator mới. Qua thử nghiệm đánh giá trên các hệ thống tương tự SCN thì quá trình CamShift có trễ dưới 3 giây [DSC_06]. Trễ này là chấp nhận được trong giám sát an ninh khu vực dân sự. 33 Ví dụ như tốc độ di chuyển lớn hơn 2.5m/s trong vùng bảo vệ ngoài giờ HC; không đi thẳng mà cúi khom người hoặc có mang vác vật bất thường. Những giá trị đặc trưng này không thể chỉ nhận biết được từ một camera đơn lẻ. 34 Ví dụ như chuyển độ phân giải quan sát hay tốc độ khung khi ghi hình. Đề xuất trường hợp xấu nhất là đưa nhiệm vụ snapshot lên mức QoS cao nhất và truyền cảnh báo về BS. 89 7.3 TỔNG KẾT VÀ BÀN LUẬN Chương 7 tập trung bàn luận về vấn đề cân bằng tải và phân chia nhiệm vụ giam sát trong SCN. Dạng bài toán CB1 này là nền tảng cho việc phát triển ứng dụng trong SCN. Thực tế cho thấy hệ thống phải có chiến lược xử lý phân tán CSP đáp ứng thời gian thực nên việc ứng dụng các tác tử di động là hoàn toàn hợp lý. Các kết quả thu nhận được tại đây là: - Khi thiết kế: việc chia hệ thống thành các nhóm s_clu ngoài những lợi điểm có được khi định tuyến ZRP, đánh địa chỉ AFA, đồng bộ bộ đếm RBS còn góp phần giảm thiểu không gian lời giải của CSP. Các s_clu này có thể chồng lẫn nhau và liên kết trong đó có thể thay đổi khi hoạt động bởi sự đảm nhiệm của các tác tử di động. - CSP phân tán là giải pháp chính tắc và hiệu quả cho s_clu khi bổ sung (loại bớt) nhiệm vụ giám sát. Nhằm phân chia nhiệm vụ cho các SC, cần sử dụng hướng tiếp cận phân tán theo vùng miền, để xử lý các CSP cục bộ mà vẫn tiết kiệm được chi phí truyền thông. - Nhằm tìm ra lời giải khả dụng và lược bớt sớm trong cây lời giải, cần định nghĩa các hàm lượng giá, trong đó tích hợp các lớp chi phí khác nhau nhằm mô tả mục tiêu đúng nhất. Các chi phí liên quan đến tài nguyên phần cứng cần được lưu ý để đảm bảo đáp ứng thời gian thực của nhiệm vụ giám sát. - Hàm lượng giá được tích hợp ngay từ những tầng thấp của thuật toán CSP để có thể giảm bớt không gian tìm kiếm ngay từ những tầng này nhằm tăng hiệu năng chung. - Việc phân chia nhiệm vụ phải hướng sự kiện và tự động bởi các tác tử di động trong SC. 90 - Khi ước lượng: SC phải tiên đoán được khả năng đáp ứng về thời gian khi tham gia vào nhiệm vụ liên kết. 91 CHƯƠNG 8 : LƯU TRỮ NỘI DUNG TRONG SCN Nếu bài toán CB1 liên quan đến hiệu năng hoạt động hiện thời của SCN thì bài toán CB2 liên quan đến quá khứ của hệ thống. Trong các hệ thống an ninh giám sát khả năng tra cứu lần vết, dò tìm thông tin trong kho lưu trữ cũng là một tiêu chí đánh giá quan trọng. Các dữ liệu trong quá khứ thường được sử dụng với mục đích tìm kiếm các hình ảnh bất thường trong sự kiện, phân tích hành vi ... Các ứng dụng lưu trữ nội dung thông tin trong những hệ thống phân tán đã được nghiên cứu và triển khai trong nhiều năm gần đây. Trong SCN các SC thu thập số liệu hình từ môi trường và phát sinh dữ liệu cho việc xử lý lọc, chuyển đổi và lưu trữ cung cấp hạ tầng thông tin chung cho người dùng. Lưu trữ nội dung thông tin bao gồm những điểm chính sau: nơi lưu trữ số liệu, các đánh chỉ mục dữ liệu và các ứng dụng truy xuất các thông tin này như thế nào để tối thiểu hóa trễ truyền thông. Cách tiếp cận đơn giản nhất là dòng dữ liệu sự kiện được truyền về điểm tập trung BS, tại đó đánh chỉ mục dữ liệu để phục vụ trong những truy xuất sau này. Tuy nhiên trong hệ thống động, năng lượng hạn chế, đa bước truyền như SCN thì biện pháp này là không hiệu quả. Cách tiếp cận khác là các SC lưu trữ dữ liệu và sự kiện cục bộ (ví dụ như ghi vào thẻ nhớ Flash) do đó các thao tác ghi là tại chỗ và không cần truyền thông. Yêu cầu truy xuất, ví dụ như một sự kiện tại một SC thành viên, dưới hình thức một thông điệp yêu cầu sẽ được gửi đến SC đó và đề nghị xử lý. Trong những hệ thống nhỏ, yêu cầu đơn lẻ, đơn giản thì mô hình này là khả thi tuy nhiên xác suất tìm kiếm thành công thấp trong môi trường quảng bá như SCN, dẫn đến trễ yêu cầu cao. Các nghiên cứu như Directed Diffusion có mang lại một số hiệu quả nhất định, cải thiện khả năng tìm đọc dữ liệu bởi 92 cơ chế định tuyến thông điệp thông minh nhưng chưa trọn vẹn cho vấn đề này. Ngoài ra còn có các hướng tiếp cận lai giữa hai hướng trên như Geographic Hash Table (GHT) sử dụng cách đánh chỉ mục nội mạng cho lưu trữ nội dung phân tán hoàn toàn tại các SC. Trong phương pháp này, mỗi nội dung dữ liệu có khóa tương ứng và phân bổ trong bảng băm. Do đó, việc ghi dữ liệu sẽ được gửi đến bảng băm nút và cập nhật vào bảng băm nội mạng. Yêu cầu tìm đọc dữ liệu sẽ truy vấn trong bảng băm nội mạng để định vị nút lưu dữ liệu, từ đó tìm đến vị trí tương ứng của dữ liệu trong bảng băm nút. Phần lớn các cách tiếp cận trên đều giả định hệ thống phẳng, thuần nhất và các SC đều có năng lượng tương đương. Trong hệ thống SCN thì đặc điểm dữ liệu hình có những điểm riêng khác các hệ khác là: - Phương pháp nén lưu trữ khác nhau phù hợp cho các ứng dụng khác nhau. - Dữ liệu đa phân giải: các khung hình CIF, QCIF, VGA ... phù hợp cho nhiều yêu cầu giám sát khác nhau. - Tốc độ khung hình: 2, 10, 15, 25 .... khung hình trên giây phù hợp cho nhiều yêu cầu giám sát khác nhau. - Ảnh tĩnh có thể coi là trường hợp đặc biệt của dòng dữ liệu hình. - Ảnh màu và ảnh đa mức xám có ứng dụng khác nhau tùy theo ứng dụng. Qua nhiều nghiên cứu và ứng dụng, người ta xây dựng nên kiến trúc lưu trữ TSAR35 [TSAR_05] phản ánh và xác định được tính tự nhiên và đa lớp của các mạng cảm biến cảnh báo và có thể ứng dụng trong SCN. TSAR là thành phần của kiến trúc lưu trữ PRESTO là hợp nhất của lưu trữ nội dung với cơ chế đệm và sự tiên đoán. 35 Two Tiers Sensor Storage Architecture 93 Một lợi điểm của những kiến trúc lưu trữ như thế này là dung lượng lưu trữ của bộ nhớ Flash cũng tăng không ngừng theo định luật Moore. Các thiết bị lưu trữ Flash hiện nay yêu cầu rất ít năng lượng cho việc ghi và xóa thông tin. Kiến trúc TSAR lợi dụng việc lưu dữ liệu và sự kiện cục bộ trên thiết bị lưu trữ Flash tại mỗi SC. Các SC chỉ gửi thông tin định danh rút gọn, còn gọi là metadata đến proxy. Tùy theo ứng dụng mà metadata có thể nhỏ hơn nhiều lần so với dữ liệu gốc. Các proxy tương tác lẫn nhau để tạo thành hệ chỉ mục phân tán cho các dữ liệu trong hệ thống. Hệ chỉ mục này cung cấp khung nhìn rộng, logic của các dữ liệu lưu trữ và cho phép các ứng dụng xuất hàng đợi cũng như tìm đọc dữ liệu quá khứ. Cơ chế look-up này làm giảm bớt các truy vấn tìm đọc trong hệ thống và giảm mức tiêu thụ năng lượng chung. Bảng 7. So sánh tính năng các hệ lưu trữ nội dung HÊ THỐNG DỮ LIỆU CHỈ MỤC ĐỌC GHI SẴN SÀNG Lưu trữ tập trung Tập trung Chỉ mục tập trung Tại điểm lưu trữ Gửi đến điểm lưu trữ Có Lưu trữ cục bộ tại nút Phân tán Không Tìm kiếm rộng, định hướng Cục bộ Không GHT/DCS Phân tán Nội mạng Bảng băm nút Gửi đến vị trí băm trong nút Không TSAR/ PRESTO Phân tán Phân tán tại các proxy Tìm kiếm Proxy, hàng đợi nút Cục bộ và cập nhật chỉ mục Có Việc thiết kế theo mô hình TSAR mang lại bốn lợi điểm: - Cốt lỗi của kiến trúc TSAR là kiến trúc đánh chỉ mục phân tán dựa trên interval skip graph. Kiến trúc này có thể lưu trữ tổng hợp các dữ liệu của SC và tổ chức của chúng nhằm mục đích tìm kiếm dễ dàng. Cấu trúc dự liệu có độ phức tạp tìm kiếm và cập nhật là ( )nlogΟ . - Tại mức SC, mỗi SC tự bảo trì nội dung thông tin được lưu trữ trong thiết bị nhớ Flash. Trong kiến trúc lưu trữ này, các trạng thái tại SC 94 được lưu trong chỉ mục metadata theo luật xa gần, multi-resolution. Các cấu trúc chỉ mục được bảo trì tại các proxy và chỉ những yêu cầu trực tiếp hoặc các hàng đợi đơn được định hướng xuống SC. Lưu trữ tại SC ở xa có hiệu quả phụ thuộc vào proxy. Các lưu trữ cục bộ được tối ưu cho các truy nhập theo chuỗi thời gian hay phục vụ các ứng dụng có tần xuất sử dụng cao. Các SC theo chu kỳ sẽ gửi thông tin trạng thái tổng hợp của chúng về proxy. Tại đây với cơ chế đánh giá cache-hit cache-miss sẽ có điều chỉnh tương ứng thông báo ngược lại các SC. - Xây dựng nguyên mẫu của TSAR dạng đa lớp là tổng hợp của các proxy dạng Stargate và các SC dạng Mote. Việc triển khai hỗ trợ nền không-thời gian, giá trị nội dung và hàng đợi dựa trên khoảng cách của dữ liệu. - Thử nghiệm TSAR bởi kết hợp EmStar/EmTOS lên nguyên mẫu, đánh giá các trễ của hàng đợi end-to-end trong mạng đa bước truyền. 8.1 CHỌN LỰA THIẾT KẾ Mô hình hệ thống Hình 16. Kiến trúc TSAR với proxy và SC 95 Các SC đóng vai trò proxy quản lý chỉ mục cho nhiều SC lân cận và cũng không hạn chế việc một SC được đánh chỉ mục trong nhiều proxy. Các proxy trao đổi thông tin theo mô hình đồ thị. Mô hình sử dụng Việc thiết kế các hệ lưu trữ như TSAR phụ thuộc vào các truy vấn sẽ xuất hiện trong hệ thống. Các SC cung cấp dữ liệu hình và có hai thuộc tính chính của thông tin này là thời điểm và địa điểm phát sinh sự kiện. Các ứng dụng thông thường chỉ truy vấn các thông tin liên quan thời gian và địa điểm của sự kiện. Có vài cách sắp xếp và phân loại các truy vấn này ví dụ như xây dựng bảng băm dự phòng cục bộ như DIMS. Các ứng dụng còn có thể xuất các truy vấn dựa trên giá trị nội dung. Và thường thì giá trị nội dung v này nằm trong một khoảng giá trị (v1,v2) thay vì là một giá trị nhất định. Việc đánh chỉ mục các truy vấn loại này dựa trên việc quản lý các thông tin tóm tắt từ SC gửi đến proxy. Các truy vấn sử dụng các thông tin tóm tắt của các thời gian và nội dung cũng có thể xuất hiện trong hệ thống. Những truy vấn này yêu cầu được đánh chỉ mục dựa trên cả thời gian và giá trị nội dung. Nguyên lý thiết kế Việc thiết kế giải pháp lưu trữ cho SCN được xây dựng dựa trên các nguyên tắc sau: - Store locally, access globally kỹ thuật lưu trữ cục bộ được xây dựng dựa trên so sánh mức tiết kiệm năng lượng so với lưu trữ mạng, và ước tính rào cản này không thể vượt qua trong tương lại gần. Tuy nhiên công tác lưu trữ phải được tối ưu cho các nhu cầu truy vấn của ứng dụng và tạo nên một giao diện lô gíc đơn nhất với ứng dụng và cân bằng giữa chi phí truyền thông và lưu trữ. 96 - Distinguish data from metadata dữ liệu cần được xác định như là tự giới thiệu với ứng dụng tránh để phải tìm kiếm vét cạn. Để thực hiện điều này, phải tổ chức metadata với mỗi bản ghi dữ liệu có các trường dữ liệu với quy tắc tường minh nhằm giúp cho việc xác định hoặc tổ chức hàng đợi trong hệ thống lưu trữ36. Việc cung cấp những metadata như vậy sẽ giúp proxy đánh chỉ mục metadata và có khung nhìn logic tổng quát của mọi dữ liệu trong hệ thống. Điều này làm tăng hiệu năng hệ thổng, giảm trễ truy vấn và thêm nhiều chức năng hữu dụng. - Provide data-centric query support trong các ứng dụng cần chỉ rõ vị trí bản ghi dữ liệu thì hệ thống phải cung cấp được dòng dữ liệu tuần tự như là thông tin được truyền tải liên tục từ điểm truyền thông theo thời gian và vị trí xác định. Để làm được điều này cần phải thường xuyên bảo trì thông tin metadata nhằm làm giảm thiểu giá tìm kiếm và theo dõi thông tin. Thiết kế hệ thống Với thiết kế TSAR, việc ghi các sự kiện được thực hiện được thực thi tại SC, tuy nhiên trong ứng dụng chỉ bắt được đặc tả nội dung trong metadata. metadata giúp ứng dụng xác định vị trí và dạng bản ghi dữ liệu cần truy xuất. Tùy thuộc vào ứng dụng mà metadata có bao gồm 2 hoặc 3 yêu cầu soi phóng to thông tin từ bản thân dữ liệu, cũng giống như metadata trích chọn đặc trưng của ảnh hay dữ liệu hình hay cung cấp khung nhìn đa phân giải theo yêu cầu. Nhằm bổ sung cho việc lưu trữ dữ liệu cục bộ, mỗi SC theo chu kỳ cần được cập nhật thông tin tóm tắt cho các proxy gần nó. Tổng hợp này bao gồm 36 Trong Metadata ngoài các thông tin như địa điểm, thời gian cần phải có các thông tin đặc thù của dữ liệu hình hay giá trị đặc trưng được kết xuất từ dữ liệu (tọa độ khung nhìn, độ sáng bình quân, ngưỡng phát hiện chuyển động, entropy, mặt nạ Law ...). 97 thông tin như địa chỉ SC, khoảng thời điểm (t1, t2), con trỏ đến vị trí lưu trữ trên thiết bị nhớ Flash... Proxy sử dụng thông tin tóm tắt trên để tạo ra bảng chỉ mục. Bảng chỉ mục là toàn cục và lưu trữ tất cả các thông tin về các SC tuy nhiên nó được lưu trữ bộ phận phân tán tại các proxy. Do vậy tuy hệ thống là phân tán nhưng ứng dụng nhìn nhận và truy nhập dữ liệu như là hàng đợi cổ điển. Đặc biệt mỗi hàng đợi là không đơn nhất mà là một dãy các hàng đợi thỏa mãn điều kiện tìm kiếm. Có một vài phương pháp thiết lập và duyệt chủ mục phù hợp cho những ứng dụng cụ thể và phương pháp trình bày dưới đây là phương pháp hiệu quả nhất. Do việc các chỉ mục được xây dựng từ những tổng hợp chung thay vì dữ liệu thực nên việc lần tìm chỉ mục sẽ chỉ kết quả gần chính xác. Lợi điểm của kỹ thuật tổng hợp TSAR là đảm báo kết quả tìm kiếm không bao giờ thất bại hoàn toàn - false negatives. Tuy nhiên trường hợp lần chỉ mục bị false positives cũng có thể xảy ra khi đối sánh đúng thông tin tóm tắt nhưng lần tìm tại SC lại không thỏa mãn. Các SC có thể phân biệt các false positive từ hàng đợi của kết quả tìm kiếm và tính toán được tỷ lệ của chúng. Dựa trên tỷ lệ này TSAR sẽ phát triển kỹ thuật động thích hợp để cân bằng giữa metadata và false positives. 8.2 CẤU TRÚC DỮ LIỆU Ở lớp proxy, TSAR thực hiện cấu trúc đánh chỉ mục gọi là Interval Skip Graph nhằm mục đích tìm kiếm nội tại cấu trúc dữ liệu phân tán có điểm hoặc khoảng giá trị thành phần. Interval skip Graph là sự kết hợp của Interval Tree - cây tìm kiếm nhị phân dựa trên thời gian, và Skip Graph - cấu trúc dữ liệu phân tán cho hệ thống ngang hàng [SG_03]. 98 Đầu tiên, độ phức tạp tìm kiếm sẽ là ( )nlogΟ cho lần truy nhập khoảng thời gian đầu tiên phù hợp giá trị nội dung và độ phức tạp là hằng cho truy nhập các khoảng thời gian phù hợp tiếp theo. Tiếp theo, việc đánh chỉ mục dựa trên khoảng thời gian thì tốt hơn là đánh chỉ mục dựa trên giá trị tổng hợp nội dung. Giả định ban đầu có NP proxy và NS SC trong mạng SCN 2 lớp. Mỗi proxy phục vụ cho nhiều SC và không có giới hạn cụ thể cho số lượng này. Mỗi SC truyền nội dung tổng hợp theo khoảng thời gian của dữ liệu hay sự kiện đến một hoặc vài proxy, trong đó khoảng thời gian i được đại diện bởi [lowi, highi]. Những khoảng thời gian này có thể có thể bao gồm thời điểm hoặc khoảng giá trị dùng cho đánh chỉ mục dữ liệu. Sẽ không có giả định gì về độ rộng của khoảng thời gian hoặc về quãng cách giữa các khoảng thời gian đó. Phạm vi các hàng đợi dựa trên khoảng thời gian được đưa ra bởi người dùng đến mạng các proxy và SC. Mỗi hàng đợi q cần thiết để xác định mọi giá trị chỉ mục về khoảng thời gian [lowq, highq]. Kết quả của interval skip graph là đánh chỉ mục mọi khoảng thời gian như là một danh mục tuần tự. Skip Graph Một skip list là một mở rộng của danh sách liên kết đơn thông thường, tuy nhiên để tăng hiệu quả tìm kiếm người ta sẽ bổ sung các con trỏ đến nút xa hơn thay vì chỉ duy trì con trỏ tuần tự [SL_90]. Mức 0 của một skip list là danh sách kết nối đến mọi nút theo sắp xếp tăng của khóa. Cho mỗi i lớn hơn không, mỗi nốt ở mức i-1 xuất hiện trong mức i độc lập với một vài xác suất p cố định. Trong doubly-linked skip list, mỗi nút lưu con trỏ đến trước và trỏ đến sau trong mỗi danh sách nó xuất hiện, tức là có trung bình p−1 2 con trỏ cho mỗi nút. Các danh sách ở nút cao hơn giúp cho việc tìm duyệt nhanh hơn. 99 Quá trình tìm kiếm bắt đầu ở nút mức cao, và tuần tự xuống mức thấp hơn chỉ khi chắc chắn nút cần tìm không có ở mức đó. Do không có nhiều hơn p−1 1 nút tại mỗi mức nên thời gian tìm kiếm trung bình sẽ là ( ) ⎟⎟ ⎟⎟ ⎠ ⎞ ⎜⎜ ⎜⎜ ⎝ ⎛ − Ο p p n 1log1 1log với n nút ở mức 0. Hình 17. Một skip list và skip graph với n = 6 nút và [log n] = 3 mức Một skip list đơn thì thiếu dự phòng và chịu lỗi, nên phải được nâng cấp thành skip graph với membership vector m(x). m(x) là một từ ngẫu nhiên từ một vài chữ cái cố định và chỉ độ dài ( )nlogΟ tiền tố của m(x) cần được tạo bởi giá trị trung bình. Đề xuất sử dụng membership vector là liên kết mọi danh sách trong skip graph được đánh nhãn bởi một vài từ w xác định, và nốt x trong danh sách được đánh nhãn w khi và chỉ khi w là tiền tố của m(x). Các thuộc tính của Skip Graph gồm có: - Ordered index các khóa là các số nguyên có thứ tự. Viêc tìm kiếm bao gồm việc so sánh khóa với chỉ mục hiện tại. Thêm vào đó, các con trỏ ở mức thấp nhất trỏ đến hạng mục kế tiếp trong bảng chỉ mục. - In-place indexing các phần tử dữ liệu vẫn nằm trên SC khi nó được chèn vào, các thông điệp được truyền giữa các nút để thiết lập liên kết giữa những phần tử với nhau trong bảng chỉ mục. - nlog height có tất cả nlog con trỏ liên kết với mỗi phần tử trong đó n là số các phần tử được đánh chỉ mục. Mỗi con trỏ thuộc một mức l trong 100 khoảng [ ]1log...0 2 −n và liên kết với các con trỏ khác ở cùng mức tạo thành chuỗi ln 2/ phần tử. - Probabilistic balance thay vì sử dụng biện pháp tái cân bằng, skip graph sử dụng kỹ thuật cân bằng ngẫu nhiên đơn giản nhằm bảo trì gần với cân bằng hoàn hảo với sai khác nhỏ. - Redundancy và resiliency mỗi phần tử dữ liệu nằm trong cây tìm kiếm độc lập, do vậy việc tìm kiếm có thể bắt đầu từ mọi nút trong mạng, loại bỏ có điểm chốt trong gốc tìm kiếm đơn. Thêm vào đó, nếu chỉ mục trỏ đến nút lỗi, có nghĩa là dữ liệu trong nút lỗi không thể truy nhập được, thì các phần tử dữ liệu còn lại vẫn có thể truy nhập trong qua cây tìm kiếm với gốc là nút khác. Các con trỏ có thể đến từ những phần tử dữ liệu đơn trong cây nhị phân. Con trỏ duyệt từ mức cao nhất với n/2 phần tử, n/4 ở mức tiếp theo và tiếp tục. Việc tìm kiếm là duyệt giảm dần từ mức cao nhất đến mức 0, tại mỗi mức so sánh khóa với phần tử tiếp theo trong mức và quyết định khi nào dừng duyệt. Trong trường hợp cây cân bằng hoàn hảo như tại đây có n2log mức thì việc tìm kiếm chỉ có 0 hoặc 1 con trỏ tại mỗi mức. Do đã giả định là các dữ liệu nằm tại các nút khác nhau nên giá trị đo của tìm kiếm là số các thông điệp được truyền nhận và có độ phức tạp tìm kiếm là ( )nlogΟ . Quá trình cập nhật cây từ dưới lên như là B-Tree với gốc được nâng lên tại mỗi mức như là cây sinh trưởng. Bằng cách này, hai chuỗi tại mức 1 luôn bao gồm n/2 thực thể và không bao giờ cần tách chuỗi khi bổ sung cấu trúc. Việc cập nhật bao gồm việc chọn lựa trong 2l chuỗi để chèn vào một phần tử tại mỗi mức l. Việc bảo trì skip graph cân bằng dựa trên việc theo dõi các phần tử thuộc chuỗi thành phần ở mức l chỉ có thể thuộc một trong 2 chuỗi mức l+1. 101 Để chèn một phần tử phải bắt đầu từ mức 0 và chọn ngẫu nhiên 1 trong 2 chuỗi có thể tại mỗi mức và dừng lại khi đến một chuỗi rỗng. Ý nghĩa của việc triển khai trên là mỗi phần tử tương ứng với một chuỗi bút ngẫu nhiên. Mỗi chuỗi tại mức l được cấu thành bởi những bit có cùng l bit đầu tiên, nên có 2l chuỗi có thể tại mỗi mức và chuỗi chia chính xác làm 2 tại mức tiếp theo. Interval Skip Graph Một skip graph được sử dụng để lưu trữ nội dung đơn, để lưu trữ khoảng thời gian [lowi, highi] cho cho phép tìm kiếm hiệu quả mọi khoảng thời gian mọi giá trị v, thì cần phải nâng cấp. Cấu trúc dữ liệu có thể mở rộng phạm vi tìm kiếm theo cách trực tiếp. Interval Skip Graph được xây dựng bởi việc ứng dụng phương pháp cây tìm kiếm có tham số cho cây tìm kiếm nhị phân tạo bởi Interval Tree. Đặc điểm của Interval Tree là mỗi nút của nó quản lý thông tin cho một đoạn con và mỗi nút sẽ có hai nút con quản lý 2 đoạn con cuả đoạn được quản lý bởi nút đó. Phương pháp này dựa trên việc quan sát cấu trúc tìm kiếm bởi việc so sánh khóa trong cây nhị phân có thể dùng tiếp để tìm khóa thứ hai không bé hơn khóa đầu tiên. Với một tập các khoảng thời gian đã sắp xếp theo thứ tự không giảm 1+≤ ii lowlow , người ta định nghĩa khóa tiếp theo như là tổng tối đa ( )kiki high...0maxmax == . Tập các khoảng thời gian có bao gồm thời điểm v có thể được tìm kiếm theo khoảng thời gian bắt đầu (khoảng thời gian có lowi thấp nhất) mà .max vi ≥ Khi đó duyệt cây theo giá trị tăng của chặn dưới cho đến khi gặp khoảng thời gian đầu tiên mà lowi > v, và chọn những khoảng thời gian này cho intersect v. Với cách tiếp cận này, người ta đã tham số hóa cấu trúc dữ liệu skip graph với mỗi đầu vào lưu trữ một khoảng (chặn dưới và chặn trên) và khóa 102 thứ hai (tính từ giá trị tối đa của chặn trên). Để tính khóa thứ hai maxi cho đầu vào i, người ta sử dụng highi và giá trị tối đa được thông báo bởi mỗi lân cận trái của i. Để tìm kiếm những khoảng thời gian có chứa thời điểm v, đầu tiên người ta tìm kiếm v trong bảng chỉ mục thứ hai maxi, và định vị đường vào đầu tiên có vi ≥max .Nếu lowi > v thì khoảng thời gian này không chứa v và các khoảng thời gian tiếp theo cũng vậy nên dừng lại. - Lookup Complexity có độ phức tạp tìm kiếm là ( )nlogΟ . - Insert Complexity trong trường hợp xấu nhất là ( )nΟ . Sparse Interval Skip Graph Trong phần trước đã chỉ ra rằng chi phí chèn và xóa trong Interval Skip Graph trong trường hợp xấu nhất có độ phức tạp là ( )nΟ so với ( )nlogΟ của Interval tree. Nguyên nhân chính của sự khác biệt này là skip graph có một cấu trúc tìm kiếm đầy đủ với gốc là mỗi phần tử để phân tải và chịu lỗi trong hệ thống phân tán. Trong TSAR thì số lượng nút proxy là nhỏ so với số SC (có dữ liệu tổng hợp được đánh chỉ mục) nên dẫn đến tiết kiệm đáng kể khi xây dựng full search. - Implementation độ phức tạp là ( )1log2 Ο+PN , trường hợp xấu nhất là nNP 2log - Short-cut search trung bình là ( )1log2 Ο+PN bước, ước tính độ phức tạp là ( )PNlogΟ Bảng 8. So sánh các phương pháp đánh chỉ mục Range Query Support Interval Representation Re- balancing Resilience Small Networks Large Network DHT,GHT no no no yes good good Local index, flood query yes yes no yes good bad 103 P-tree, RP* (distributed B-Tree yes possible yes no good good DIMS yes no yes yes yes yes Interval Skip Graph yes yes no yes good good 8.3 LƯU TRỮ DỮ LIỆU VÀ THÔNG TIN TÓM TẮT Ở mức các SC bình thường, TSAR triển khai hai kỹ thuật quan trọng. Thứ nhất, là kỹ thuật lưu trữ cục bộ tại SC với tiêu chí tối ưu cho các thiết bị có dung lượng nhớ cố định. Thứ hai, kỹ thuật tổng hợp thông tin thích hợp cho phép SC có thể thay đổi tính chất của dữ liệu và hàng đợi. Lưu trữ cục bộ tại SC Interval skip graph cung cấp một kỹ thuật hiệu quả để tìm kiếm các nút SC chứa dữ liệu cần cho hàng đợi. Những hàng đợi này sẽ được định tuyến đến SC, nơi lưu giữ những bản ghi và phản hồi ngược đến proxy. Để cho phép những tìm kiếm kiểu này, mỗi SC trong TSAR tự bảo trì một các bản ghi cục bộ. Tất nhiên, do có giới hạn về tài nguyên và năng lượng nên việc bảo trì dữ liệu cục bộ phải được cân đối trong phạm vi đó. Ngoài các dữ liệu hình thuần túy cần cân nhắc giữa đa phân giải, sắc màu và tốc độ khung thì các bản ghi còn bao hàm nhiều loại dữ liệu khác nhau như dòng dữ liệu theo thời gian streaming media, dữ liệu tạm, các dữ liệu đã qua xử lý như biến đổi FFT, biến đổi Wavelet, clustering, đối sánh hay trích chọn đặc trưng ... Timestamp Calibration Parameters Data/Event Attributes size Opaque Data Hình 18. Bản ghi lưu trữ đơn Các dữ liệu lưu cục bộ được tập hợp thành các bản ghi và nối vòng logic. Các bản ghi mới được xếp vào đuôi của vùng đệm. Hình 21 là biểu diễn 104 khuôn dạng của mỗi bản ghi: gồm có trường metadata bao gồm các nhãn thời gian, chỉ số SC, thông số chung ... Các dữ liệu hình thuần túy được lưu trong trường dữ liệu của bản ghi này. Trường dữ liệu được coi là như là nguyên khối trong đặc tả ứng dụng vì các thông tin chung đã được đưa vào trong metadata do vậy hệ thống lưu trữ không cần quan tâm chi tiết đến trường này. Như trong các hệ xử lý ảnh camera thì các ảnh nhị phân là rất nhiều và có thể xếp vào trường dữ liệu vì những thông tin như texture, histogram, bit length ... đã được tính và đặt trong metadata. Cuối cùng, TSAR hỗ trợ độ dài biến đổi của trường dữ liệu, ví dụ kích cỡ của bản ghi có thể phụ thuộc vào giá trị trong metadata của bản ghi khác. Ba toán tử có tác động trực tiếp lên hệ lưu trữ tại đây là: khởi tạo, đọc và xóa. Trong đó việc khởi tạo là đơn giản và tường minh, đơn giản chỉ cần tạo bản ghi mới và gắn vào cuối trong chuỗi lưu trữ. Do luôn ghi vào cuối nên hệ lưu trữ luôn phải giám sát và định vị danh sách chỗ trống. Mọi trường trong bản ghi cần được đặc tả ngay tại thời điểm khởi tạo, để có thể tính toán được kích thước chuẩn của bản ghi và số byte mất đi dành cho việc lưu trữ bản ghi này. Thao tác đọc nhằm mục đích đáp ứng các hàng đợi được sinh ra từ ứng dụng. Trong các cơ sở dữ liệu truyền thông, việc tìm kiếm hiệu quả do việc luôn bảo trì B-tree các khóa chỉ mục. Tuy nhiên với những SC có giới hạn tài nguyên thì việc này là không đơn giản. Thường thì TSAR SC không bảo trì chỉ số nào trong danh sách lưu trữ cục bộ mà chỉ cung cấp metadata theo chu kỳ đến proxy và lưu một cảnh báo về vị trí của các bản ghi trong bộ nhớ flash. Dù cho dung lượng lưu trữ cục bộ có thể mở rộng, nhưng vẫn có lúc cần ghi đè lên dữ liệu cũ, đặc biệt là trong các ứng dụng đòi hỏi tốc độ dữ liệu cao. Điều này được thực hiện bởi kỹ thuật lưu trữ đa phân giải sẽ được trình bày kỹ lưỡng trong phần dưới hoặc đơn thuần chỉ ghi đè dữ liệu cũ. Thao tác 105 xóa bao gồm xóa chỉ mục trên interval skip graph tại proxy và vùng lưu trữ tương ứng trong bộ nhớ flash của SC được giải phóng. Tóm tắt theo nhu cầu - Adaptive Summarization Việc tóm tắt dữ liệu như là hồ dính giữa lưu trữ tại SC với chỉ mục tại proxy. Mỗi cập nhật từ SC đến proxy bao gồm ba thông tin: tóm tắt nội dung, thời điểm tương ứng với tóm tắt đó và độ lệch bắt đầu/ kết thúc trên thiết bị nhớ flash. Nói chung thì proxy có thể đánh chỉ mục khoảng thời gian dựa trên thông tin tóm tắt của khoảng giá trị được ghi trong đó hoặc cả hai. Cách đánh chỉ mục cũ cho phép tìm kiếm nhanh mọi bản ghi trong thời điểm chắc chắn, trong khi cách đánh chỉ mục mới cho phép tìm mọi bản ghi đúng với giá trị đó. Như đã mô tả trong phần trước, do có sử dụng năng lượng để gửi tóm tắt (tần xuất và độ cô đọng của các tóm tắt này) nên dẫn đến xuất hiện chi phí false hit trong các hàng đợi. Việc tần xuất gửi thông tin tóm tắt thưa thì tiêu tốn ít năng lượng, tuy nhiên việc false hit lại gây tăng năng lượng khi yêu cầu không truy xuất được dữ liệu. Độ chi tiết của tóm tắt phụ thuộc vào hai tham số là thời gian khi tóm tắt dữ liệu được xây dựng và truyền đến proxy theo nhu cầu được đặc tả bởi ứng dụng. Việc thay đổi kích thước của tóm tắt này rất có giá trị trong nhiều ứng dụng. TSAR đưa ra một kịch bản tóm tắt đơn giản dựa trên tính toán tỷ lệ giữa false/true hit, giảm (tăng) interval giữa các tóm tắt khi tỷ lệ này tăng (giảm) dựa theo ngưỡng. 8.4 TỔNG KẾT VÀ BÀN LUẬN Chương 8 bàn luận về vấn đề lưu trữ nội dung phục vụ tra cứu trong SCN. Phương pháp lưu trữ được trình bày ở đây là TSAR với sự phân chia chức năng và chế độ hoạt động trong các SC thành các SC, proxy và BS. Các 106 proxy là cầu nối giữa SC và BS. Điều này cũng tương tự như chia zone trong định tuyến ZRP, một SC có thể cung cấp metadata cho nhiều proxy, và từ BS có thể truy vấn thông tin từ nhiều proxy. Các dữ liệu tại SC được lưu trữ trên thiết bị nhớ Flash, và cũng được xây dựng bảng chỉ mục cục bộ. Cũng do tài nguyên bị giới hạn nên việc đánh chỉ mục tại đây cũng không quá tinh vi có thể sử dụng phương pháp băm bình thường. Bảng băm này được bảo trì bằng cách khi có dữ liệu mới cần chèn vô chỉ mục thì sẽ kiểm tra con trỏ trong danh sách hiện thời trỏ đến dữ liệu, sử kiện có tần xuất truy nhập, thời gian lưu trữ có vượt ngưỡng đề ra hay không? Từ đó quyết định thay thế con trỏ cũ đó hay lập con trỏ mới móc nối đến dữ liệu mới. Cơ chế đánh chỉ mục tại proxy được xây dựng dựa trên Interval Tree và Skip Graph. Việc sử dụng và bảo trì các con trỏ skip dựa trên xác suất và tần suất giúp đảm bảo tăng tốc tìm kiếm trong quá trình hoạt động. Thông tin tóm tắt của một SC có thể xuất hiện ở nhiều proxy đảm bảo cho BS có khả năng chọn lựa và chịu lỗi. Việc xây dựng metadata trên có sở lưu các đặc trưng của dữ liệu hình và đa phân giải theo luật xa gần đảm bảo hệ thống luôn có phản hồi thỏa đáng đến yêu cầu ứng dụng. 107 KẾT LUẬN Những bàn luận trên đây đã chỉ ra sự ưu việt của hệ thống SCN so với các hệ thống giám sát an ninh thế hệ cũ trong những ứng dụng đòi hỏ tính chịu lỗi và thích nghi cao. Thiết kế trong chương 2 là thiết kế chuẩn chung cho các SC và các thực thể trong các mạng multimedia phân tán khác. Các vấn đề trong chương 3, 4, 5, 6 là những vấn đề cơ bản nhất của các hệ thống phân tán sử dụng truyền thông không dây kiểu ad-hoc. Chương 7, 8 đề cập đến các mô hình ứng dụng, lưu trữ và tra cứu trong hệ thống SCN. Khả năng ứng dụng SCN trong công tác giám sát an ninh đã và đang được triển khai trên thế giới. Trong giai đoạn này, đó là các ứng dụng trong quân sự và quốc phòng, hy vọng rằng trong tương lai gần sẽ có những hệ thống SCN thương mại phục vụ cho dân sự. Việc phát triển các hệ thống giám sát an ninh cho các công trình xây dựng dân dụng và các khu đô thị việc nghiên cứu SCN là cần thiết và khả thi trong xu hướng phát triển chung của các mạng nội bộ và mạng khu vực. Trong điều kiện hiện nay, hướng ứng dụng các sản phẩm thương mại có sẵn và tự phát triển các ứng dụng, kịch bản giám sát là phù hợp với nhân lực và trình độ kỹ thuật chung ở Việt nam. Để có thể hoàn toàn làm chủ được công nghệ và chủ động triển khai hệ thống cần có sự phối hợp của các chuyên gia từ nhiều nhóm ngành khác nhau và tham khảo thêm các hệ thống tương tự hiện đã có trên thế giới. Kiến nghị về những nghiên cứu tiếp theo Tìm kiếm các phương pháp đánh chỉ mục dữ liệu, tổng hợp thông tin metadata khác không dựa trên kỹ thuật interval. 108 Xây dựng SCN mới với truyền thông hybird nhằm tận dụng những công nghệ truyền thông vô tuyến mới sẵn có hoặc đang thử nghiệm ở Việt nam. 109 TÀI LIỆU THAM KHẢO Tiếng Anh [TCP_04] Adam Dunkels, Juan Alonso, Thiemo Voigt (2004), Making TCP/IP Viable for Wireless Sensor Networks, [SPI_01] Adrian Perrig, Robert Szewczyk, Victor Wen, David Culler, J.D. Tygar (2001), SPINS: Security Protocols for Sensor Networks, Mobile Computing and Networking 2001 Rome, Italy. [DOS_02] Anthony D.Wood, John A.Stankovic (2002), Denial of Service in wireless Sensor Networks, University of Virginia. [SS_03] Arun Hampapur, Lisa Brown, Jonathan Connell, Sharat Pankanti, Andrew Senior, Yingli Tian (2003), Smart Surveillance: Applications, Technologies and Implications , IEEE Pacific-Rim Conference On Multimedia. Singapore. [AHN_00] Charles E. Perkins (2000), Ad Hoc Networking with AODV, Nokia Research Center - powerpoint slide. [AODV_97] Charles E. Perkins, Elizabeth M. Royer (), Ad-hoc On-demand Distance Vector Routing , MILCOM '97 panel on Ad Hoc Networks, Nov. 1997. [ZERO_01] Erik Guttman (05 - 2002), Autoconfiguration for IP Networking: Enabling Local Communication, IEEE Internet Computing 1089-7801/01. [SMD_05] Huan Li, Prashant Shenoy, Krithi Ramamritham (03-2005), Scheduling Messages with Deadlines in Multi-hop Real-time Sensor Networks, IEEE Real-Time and Embedded Technology and Applications Symposium (RTAS 2005) 110 [SG_03] James Aspnes, Gauri Shah (2003), Skip Graphs, In Proceedings of the 14th Annual ACM-SIAM Symposium on Discrete Algorithms, Jan. 2003. [ZRP_02] Jan Schaumann (12 - 2002), Analysis of the Zone Routing Protocol, [AFA_00] Jeremy Elson, Deborah Estrin (2000), An Address-Free Architecture for Dynamic Sensor Networks, Tech. Rep. 00- 724, Computer Science Department USC, January 2000. [TS_01] Jeremy Elson, Deborah Estrin (2001), Time Synchronization for Wireless Sensor Networks , UCLA CS Technical Report 200028 [RTS_02] Jeremy Elson, Kay Romer (2002), Wireless Sensor Networks: A new Regime for Time Synchronization , Proceeding of the First Workshop on Hot Topics in Networks - Princeton, New Jersey, USA. [RBS_02] Jeremy Elson, Lewis Girod, Deborah Estrin (2002), Fine- Grained Network Time Synchronization using Reference Broadcasrt, UCLA Computer Science Technical Report 020008. [BEWS_01] John Heidemann, Fabio Silva, Chalermek Intanagonwiwat, Ramesh Govidan, Deborah Estrin, Deepak Ganesan (2001), Building Efficient Wireless Sensor Networks with Low-Level Naming, as part of the SCAADS project, SCOWR project, due to support from Cisco Systems. 111 [EM_04] L. Girod, J. Elson, A. Cerpa, T. Stathopoulos, N. Ramanathan, D. Estrin (2004), EmStar: a Software Environment for Developing and Deploying Wireless Sensor Networks, in the Published as CENS Technical Report #34 [CG_06] Laura Savidge, Huang Lee, Hamid Aghajan, Andrea Goldsmith (03-2006), Event-Driven Geographic Routing for Wireless Image Sensor Networks, In Proc. of Cognitive Systems and Interactive Sensors - Paris. [SAN_99] Lidong Zhou, Zygmunt J. Hass (1999), Secure Ad Hoc Networks, IEEE network, special issus on network security, November/ December 1999. [DSC_06] Markus Quaritsch, Markus Kreuzthaler, Bernhard Rinner, Bernhard Strobl (2006), Decentralized Object Tracking in a Network of Embedded Smart Cameras, Workshop on Distributed Smart Cameras, ACM SenSys 2006. [DESC_06] Michael Bramberger, Andreas Doblander, Arnold Maier, Bernhard Rinner, Helmut Schwabach (2006), Distributed Embedded Smart Cameras for Surveillance Applications, Published by the IEEE Computer Society 0018-9162/06 p68- 75. [DDTA_05] Michael Bramberger, B. Rinner, H. Schwabach (06-2005), Distributed Dynamic Task Allocation in Clusters of Embedded Smart Cameras, Proc. Int'l Conf. Systems, Man and Cybernetics, IEEE Press. 3005. 112 [TSAR_05] Peter Desnoyers, Deepak Ganesan, Prashant Shenoy (năm), TSAR: A Two Tier Sensor Storage Architecture Using Interval Skip Graphs, National Science Foundation grants EEC- 0313747, CNS-0325868 and EIA-0098060. [GCS_04] Qun Li, Daniela Rus (2004), Global Clock Synchronization in Sensor Networks, IEEE Infocom 2004 [OGS_03] Richard Karp, Jeremy Elson, Deborah Estrin, Scott Shenker (2003), Optimal and Global Time Synchronization in Sensornets, CENS Technical Report #12 , April 2003 [DCNL_04] William E. Mantzel (11-2004), Distributed Camera Network Localization, Signals, Systems and Computers, 2004. Conference Record of the Thirty-Eighth Asilomar Conference on page(s): 1381- 1386 Vol.2 [SL_90] William Pugh (06-1990), Skip lists: a probabilistic alternative to balanced trees, Communications of the ACM, June 1990, 33(6) 668-676. Tiếng Việt [PCW_06] Công nghệ máy tính và mạng (10-2006), DaVinci đi cùng MontaVista, Thế giới vi tính PCWORLD p85-86. PHỤ LỤC 1. QUAN HỆ VỊ TRÍ KHÔNG GIAN, THỊ TRƯỜNG QUAN SÁT CỦA CÁC CAMERA VÀ THUẬT TOÁN DALT Các định nghĩa và định lý dưới đây [DCNL_04] áp dụng cho camera thông thường và cũng được sử dụng khi tính toán quan hệ vị trí và thị trường quan sát của các SC trong SCN. Định nghĩa 1 Hai camera fi và fj là có liên kết linked (biểu diễn 21 ff ↔ ) nếu khung nhìn của chúng có có cùng tập hợp 6 hoặc nhiều hơn điểm đặc trưng. Định nghĩa 2 Một mạng camera trải rộng là mạng có ít nhất một cặp camera không có liên kết. Định nghĩa 3 Một liên kết các camera tạo thành bộ ba ∆ khi các cặp camera trong chúng được liên kết với nhau đôi một. Định lý 4 Khi các camera tạo thành liên kết bộ ba ∆ thì khi biết vị trí và góc hướng của một camera (ví dụ f1) và khoảng cách từ đó đến các camera khác (ví dụ f2, f3) được biết thì có thể tính được vị trí và góc hướng đến cả ba f1, f2, f3. Định nghĩa 5 hai camera fi, fj là triple-wise connected nếu tồn tại các liên kết tam giác ∆ 1, ∆ 2, ..., ∆ n dạng như ∆ r và ∆ r+1 có hai camera chung và 1∆∈if và njf ∆∈ . Định nghĩa 6 Một microcluster là tập các camera M với đặc điểm thuộc tính là khi Mfi ∈ thì Mf j ∈ khi và chỉ khi fi là triple-wise connected với fj. Định lý 7 Mọi camera nằm trong một microcluster có thể có quan hệ vị trí toàn cục trong một hệ quy chiếu với thang độ toàn cục và với ít nhất bảy bậc tự do. Theo (ĐN 2) thì SCN được coi là một mạng camera trải rộng. Theo định lý 4, tác vụ pan khung nhìn của camera có thể tạo thành liên kết bộ ba camera mới hoặc phá hủy liên kết bộ ba cũ. Định nghĩa 5 gợi ý hướng truyền tải nội dung xử lý theo vết đối tượng trong nhiệm vụ giám sát. Định lý 7 giúp xây dựng lưới vị trí camera cho các nhiệm vụ giám sát. Các kết quả trên hữu dụng khi khởi tạo hệ thống hoặc tái cấu trúc SC trong s_clu khi đang vận hành. Thuật toán DALT được đề xuất cho việc xây dựng và tìm kiếm các camera có quan hệ vị trí và thị trường quan sát. Thuật toán DALT (distributed alternating localization triangulation) 1. if đã biết thiết vị then 2. quảng bá thông tin thiết vị này đến các camera có liên kết 3. else 4. đợi đến khi có thông tin thiết vị được quảng bá đến từ 2 hoặc hơn camera có liên kết 5. sử dụng những thông tin thiết vị của những lân cận có quan hệ bộ ba với 6 hoặc hơn điểm đặc trưng 6. khởi tạo, tính toán thiết bị của mình từ những thông tin trên 7. end if 8. repeat 9. tự quảng bả thông tin ước đoán thiết vị của mình 10 sử dụng mọi thiết vị của quan hệ bộ ba cũng như các điểm đặc trưng có thể 11 với góc hướng cố định, ước đoán chuyển dịch tối ưu 12 với chuyển dịch cố định, ước đoán góc hướng tối ưu 13 until ước đoán được hết thiết vị các camera 2. ĐỊNH TUYẾN EIRGP CỦA CISCO VÀ GIẢI THUẬT DUAL EIRGP là giao thức định tuyến độc quyền của Cisco trong mạng truyền thống và NGN. Trong EIGRP có các bảng Neighbor, bảng Topology và bảng Routing. Bảng neighbor để lưu giữ các lân cận, bảng topology chứa thông tin về tất cả các route do các lân cận gửi đến và bảng routing thì chỉ chứa tuyến đường tốt nhất. EIGRP chỉ gửi cập nhật mỗi khi có sự thay đổi và chỉ gửi thay đổi này đến những router cần thông tin đó. Sau khi các router đã nhận đầy đủ thông tin về các router khác lân cận xong thì nó sẽ sử dụng giải thuật Diffusing Update Algorithm để xác định successor và feasible successor. Successor là next hop router mà từ local router đến mạng đích thông qua router này có metric là thấp nhất (gọi là feasible distance). Còn feasible successor là next hop router mà có metric cao hơn ở trên (tất nhiên, nếu không nó đã là successor) nhưng có khoảng cách từ nó đến mạng đích (gọi là advertised distance hoặc reported distance) là thấp hơn feasible distance của successor ở trên. Successor được đặt vào routing table, còn feasiable successor thì vẫn để ở trong topology table. Khi một successor là invalid thì một feasible successor thích hợp nhất sẽ được chọn và được làm successor (mà router không cần tính lại bảng topology). Giải thuật DUAL Đây là thuật toán cập nhật lan truyền (diffusing) và có tốc độ hội tụ nhanh. Nó là lan truyền ở chỗ mỗi một router sẽ chọn tuyến đường tốt nhất đến một mạng đích bằng cách chọn một successor, rồi successor này lại chọn tuyến đường tốt nhất đến đích dựa vào successor của nó. Có nghĩa là mỗi một router chỉ cần tìm router neighbor gần nhất, rồi router neighbor gần nhất đó lại tìm tiếp một neighbor khác gần nhất để đến mạng đích. Khi một tuyến đường qua successor mà invalid mà không có feasible successor để thay thì các router cũng query theo kiểu lan truyền như vậy để tìm ra successor mới. Vì có khái niệm feasible successor nên các router không phải tính toán lại bảng topology để tìm ra tuyến đường mới sau khi invalid. Còn cơ chế chống loop là do trong quá trình lan truyền để tìm tuyến đường, DUAL sẽ đảm bảo không có sự lặp lại của mỗi một router. TÓM TẮT LUẬN VĂN Ngày nay, việc phát triển các hệ thống mạng camera phục vụ giám sát an ninh khu vực trên nền công nghệ IP đang là chuẩn hóa khi thiết kế các giải pháp phụ trợ cho các công trình xây dựng dân dụng. Tuy nhiên kiến trúc các hệ thống hiện tại là hướng cấu trúc, thiếu tự chủ, tính chịu lỗi và thích nghi chưa cao do đặc điểm hệ thống là cần có trung tâm điều khiển tập trung. Trong một vài ứng dụng cụ thể thì việc xây dựng thuật toán hoạt động trên nền kiến trúc này gặp nhiều khó khăn khi có sự biến động về số lượng camera và nhiệm vụ giám sát trong hệ thống. Luận văn này tập trung nghiên cứu về hướng xây dựng hệ thống mạng mới trên cơ sở các camera thông minh phân tán thực sự và phân tải phân tán nhiệm vụ giám sát để tạo thành hạ tầng phát triển các thuật toán trên. Hệ thống này được gọi là MẠNG CAMERA THÔNG MINH - Smart Camera Network (SCN). Trên cơ sở phân tích các vấn đề cơ bản là vấn đề đánh địa chỉ camera, đồng bộ bộ đếm phân tán, định tuyến và an ninh truyền thông, luận văn đề xuất và đưa ra giải pháp giải quyết hai bài toán cơ bản . 3. Bài toán CB1: Đánh giá tác động và cơ chế điều chỉnh phân tán nhiệm vụ giám sát cho mỗi SC trong SCN. 4. Bài toán CB2: Tìm kiếm thông tin, dữ liệu hình đã lưu trữ trong SCN. Những bài toán này là cơ sở cho việc phát triển các ứng dụng gia tăng và nghiên cứu về sau trong SCN. TỪ KHÓA mạng camera thông minh, camera phân tán, phân tán nhiệm vụ giám sát, tác tử di động, lịch truyền thông điệp ABSTRACT Nowadays, the development of camera system for the sake of security supervision basing on IP technology is becoming standardized for selection on backing solution of civil construction. However, architecture of recent system is structure driven, fault tolerance and less adaptiveness because of the short of central controlling system. In some specific application, the building of algorithm based on this architectural ground faces many difficulties when there is a change in the number of cameras as well as surveillance tasks. This thesis (dissertation) focuses on carrying out study on building new network system based on real distributed smart cameras and distributing surveillance tasks to create an developed infrastructure for above algorithm. This system is named Smart Camera Network (SCN). On the ground of basis analysis of naming camera, time synchronization, routing, semantic security, the paper puts forth and gives out suggestions to solve the two research problems. 5. Problem 1: evaluation of impact and the adjustment scatter mechanism of surveillance task for each SC in SCN. 6. Problem 2: data and information gathering archived in SCN. The mentioned problems lay out the foundation for the development of increasing application and following research on SCN. KEYWORD smart camera network, distributed camera, distributed surveillance task, mobile agent, scheduling messages