Ching-Yao Wang and Tien-Ruey Hsiang
Dept. of Computer Science and Information Engineering National Taiwan University of Science and Technology
Title: The 10th International Symposium on Pervasive Systems, Algorithms,and Networks, ISPAN 2009, Kaohsiung, Taiwan, December 14-16, 2009
Publisher: IEEE
ISBN: 978-0-7695-3908-9
http://doi.ieeecomputersociety.org/10.1109/I-SPAN.2009.106
Sensor nodes located on the boundary of the covered area often cause difficulties in maintaining a wireless sensor network's lifespan. This study proposes a simple method to approximate boundaries in wireless sensor networks. The approach uses only connectivity information of a network while not requiring nodes localize themselves. The proposed method divides a network into clusters and forms partial boundaries, then extends detected partial boundaries until the whole boundary is formed. Using a node's 1- and 2-hop neighbors, every node can decide locally whether itself is located near the boundary. The implementation shows that the approach can efficiently determine boundaries in the coverage of a WSN.
Boundary detection may provide a picture of the coverage condition of a sensor network. From boundary information, the number or motion of intruders may be induced, the weakly covered areas can be found, and the distribution of power consumption can be predicted. In this paper, an approach of topological boundary approximation for self-organizing sensor networks is proposed. The approach works in a single cluster WSN, where leaf nodes perform cycle tests. However, it requires more communication to approximate boundaries. In order to reduce the communication overhead, a clustering phase is added to first divide a WSN, then cycle tests are performed on selected nodes to approximate boundaries. Every node uses the connectivity information of its 1-hop and 2-hop neighbors to perform a cycle test in the proposed approach.
The implementation and simulations show that the proposed method successfully approximates boundaries in all cases and verified the estimation on the minimum detectable hole distance. Nodes in the proposed method require no additional communications other than forming 2-hop neighborhoods. Therefore, the developed method makes less impact on the lifespan of a WSN than other approaches. The cycle property of nodes remains the same in mobile WSNs, where sensor nodes are equipped with actuators. However, mobility implies frequent updates of the boundary condition which require complex communications. The boundary approximation in mobile sensor networks using cycle tests is currently under investigation.
Grouping:
Result:
//---------------------------------------------------------------------------
#include <vcl.h>
#pragma hdrstop
#include "main.h"
//---------------------------------------------------------------------------
#pragma package(smart_init)
TForm1 *Form1;
using namespace std;
TColor *group_color;
BoundaryDetection BD;
//---------------------------------------------------------------------------
bool sort_id(Two_Hop_Set a,Two_Hop_Set b)
{
return a.id < b.id;
}
//---------------------------------------------------------------------------
bool sort_hop_count(Two_Hop_Set a,Two_Hop_Set b)
{
return a.One_Hop_Count > b.One_Hop_Count;
}
//---------------------------------------------------------------------------
BoundaryDetection::BoundaryDetection()
{
node = NULL;
}
//---------------------------------------------------------------------------
void BoundaryDetection::Draw_Node(TImage *image,AnsiString mode, TColor color,int shift_size, int id)
{
if(mode=="Pen")
image->Canvas->Pen->Color=color;
if(mode=="Brush")
{
image->Canvas->Brush->Style=bsClear;
image->Canvas->Brush->Color=color;
}
image->Canvas->Ellipse(node[id].coordinate_x+communication_range+shift_size,node[id].coordinate_y+communication_range+shift_size,
node[id].coordinate_x+communication_range-shift_size,node[id].coordinate_y+communication_range-shift_size);
}
//---------------------------------------------------------------------------
void BoundaryDetection::initial(void)
{
int node_count=0;
ifstream fin;
fin.open(Form1->OpenDialog1->FileName.c_str(),ios::in);
fin>>node_number;
node=new Node_type[node_number];
while(!fin.eof() && node_count<node_number)
{
node[node_count].Node_ID=node_count;
fin>>node[node_count].coordinate_x>>node[node_count].coordinate_y;
Application->ProcessMessages();
Form1->Image1->Canvas->Brush->Style=bsSolid;
Draw_Node(Form1->Image1,"Pen",clBlack,2,node_count);
node[node_count].min_hop_count_to_head=0;
node[node_count].isTesting=false;
node[node_count].status="not test";
node[node_count].isAddToPath=false;
TListItem *item=Form1->ListView1->Items->Add();
item->Caption=IntToStr(node_count);
item->SubItems->Add(IntToStr(node[node_count].coordinate_x));
item->SubItems->Add(IntToStr(node[node_count].coordinate_y));
node_count++;
}
Form1->StatusBar1->Panels[0].Items[0]->Text="Node Number： " + IntToStr(node_number);
}
//---------------------------------------------------------------------------
void BoundaryDetection::Find_One_Hop_Neighbor(void)
{
total_degree=0;
for(int i=0;i<node_number;i++)
{
for(int j=0;j<node_number;j++)
{
if(i!=j)
if(!Out_Of_Range(node[i].coordinate_x,node[i].coordinate_y,node[j].coordinate_x,node[j].coordinate_y,communication_range))
node[i].One_Hop_ID.push_back(j);
}
total_degree+=node[i].One_Hop_ID.size();
}
average_degree=total_degree/node_number;
Form1->StatusBar1->Panels[0].Items[1]->Text="Average Degree： " + FloatToStr(average_degree);
}
//---------------------------------------------------------------------------
void BoundaryDetection::Find_Two_Hop_Neighbor(void)
{
for(int i=0;i<node_number;i++)
{
for(int j=0;j<node[i].One_Hop_ID.size();j++)
{
for(int k=0;k<node[node[i].One_Hop_ID[j]].One_Hop_ID.size();k++)
{
if(node[node[i].One_Hop_ID[j]].One_Hop_ID[k]!=i)
node[i].Two_Hop_ID.push_back(node[node[i].One_Hop_ID[j]].One_Hop_ID[k]);
}
}
for(int j=0;j<node[i].One_Hop_ID.size();j++)
{
node[i].Two_Hop_ID.erase( remove(node[i].Two_Hop_ID.begin(),node[i].Two_Hop_ID.end(),
node[i].One_Hop_ID[j]),
node[i].Two_Hop_ID.end()
);
}
sort(node[i].Two_Hop_ID.begin(),node[i].Two_Hop_ID.end());
node[i].Two_Hop_ID.erase(unique(node[i].Two_Hop_ID.begin(), node[i].Two_Hop_ID.end()), node[i].Two_Hop_ID.end());
node[i].to_each_head_hop_count=new int[group_number];
node[i].to_head_parent=new int[group_number];
for(int g=0;g<group_number;g++)
{
node[i].to_each_head_hop_count[g]=0;
}
}
}
//---------------------------------------------------------------------------
void BoundaryDetection::FindGroupFlooding(int ParentID ,int HeadID,int GroupID)
{
int parentHC=node[ParentID].to_each_head_hop_count[GroupID];
for(int i=0;i<node[ParentID].One_Hop_ID.size();i++)
{
childHC=parentHC+1;
if(node[node[ParentID].One_Hop_ID[i]].to_each_head_hop_count[GroupID] <= childHC)
{
if(node[node[ParentID].One_Hop_ID[i]].to_each_head_hop_count[GroupID]!=0)
;
else
{
if(node[node[ParentID].One_Hop_ID[i]].Node_ID!=node[ParentID].Node_ID)
{
node[node[ParentID].One_Hop_ID[i]].to_each_head_hop_count[GroupID]=childHC;
node[node[ParentID].One_Hop_ID[i]].to_head_parent[GroupID]=ParentID;
Application->ProcessMessages();
FindGroupFlooding(node[ParentID].One_Hop_ID[i],HeadID,GroupID);
}
}
}
if(node[node[ParentID].One_Hop_ID[i]].to_each_head_hop_count[GroupID] > childHC)
{
if(node[node[ParentID].One_Hop_ID[i]].Node_ID!=node[ParentID].Node_ID)
{
node[node[ParentID].One_Hop_ID[i]].to_each_head_hop_count[GroupID]=childHC;
node[node[ParentID].One_Hop_ID[i]].to_head_parent[GroupID]=ParentID;
Application->ProcessMessages();
FindGroupFlooding(node[ParentID].One_Hop_ID[i],HeadID,GroupID);
}
}
}
}
//---------------------------------------------------------------------------
void BoundaryDetection::Determine_Testing_Node()
{
if(group_number>1 && multiplemode==2)
{
for(int i=0;i<node_number;i++)
{
if(node[i].isLeaf==true)
{
node[i].isTestingNode=true;
testing_message_overhead=testing_message_overhead+node[i].One_Hop_ID.size()*2+node[i].Two_Hop_ID.size()*2;
total_testing_node++;
}
}
}
if(group_number>1 && multiplemode==3)
{
int min_flag;
for(int i=0;i<node_number;i++)
{
min_flag=0;
if(node[i].isLeaf==true)
{
for(int j=0;j<node[i].One_Hop_ID.size();j++)
{
if(node[i].Node_ID < node[node[i].One_Hop_ID.at(j)].Node_ID)
min_flag=1;
}
if(min_flag==0)
{
node[i].isTestingNode=true;
testing_message_overhead=testing_message_overhead+node[i].One_Hop_ID.size()*2+node[i].Two_Hop_ID.size()*2;
total_testing_node++;
}
}
}
}
if(group_number>1 && multiplemode==1)
{
for(int i=0;i<node_number;i++)
{
if(node[i].isLeaf==true)
{
int flag=0;
for(int j=0;j<node[i].One_Hop_ID.size();j++)
{
if(node[node[i].One_Hop_ID[j]].Group_ID!=node[i].Group_ID)
flag=1;
}
if(flag==1)
{
node[i].isTestingNode=true;
int two_hop_oh=0;
testing_message_overhead=testing_message_overhead+node[i].One_Hop_ID.size()*2+node[i].Two_Hop_ID.size()*2;
Draw_Node(Form1->Image1,"Pen",clRed,2,i);
total_testing_node++;
}
else
node[i].isTestingNode=false;
}
}
}
if(group_number==1 && singlemode==1)
{
for(int i=0;i<node_number;i++)
{
if(node[i].isLeaf==true)
{
testing_message_overhead=testing_message_overhead+node[i].One_Hop_ID.size()*2+node[i].Two_Hop_ID.size()*2;
total_testing_node++;
}
}
}
if(group_number==1 && singlemode==2)
{
int min_flag;
for(int i=0;i<node_number;i++)
{
min_flag=0;
if(node[i].isLeaf==true)
{
for(int j=0;j<node[i].One_Hop_ID.size();j++)
{
if(node[i].Node_ID < node[node[i].One_Hop_ID.at(j)].Node_ID)
min_flag=1;
}
if(min_flag==0)
{
node[i].isTestingNode=true;
testing_message_overhead=testing_message_overhead+node[i].One_Hop_ID.size()*2+node[i].Two_Hop_ID.size()*2;
total_testing_node++;
}
}
}
}
}
//---------------------------------------------------------------------------
void BoundaryDetection::Grouping()
{
Find_One_Hop_Neighbor();
Find_Two_Hop_Neighbor();
sel_g=new int[group_number];
flag_gorup=new int[group_number];
group_color=new TColor[10];
group_color[0]=RGB(64,0,64);
group_color[1]=RGB(115,115,0);
group_color[2]=RGB(255,128,0);
group_color[3]=RGB(0,0,255);
//generating head id
randomize();
for(int i=0;i<group_number;i++)
{
sel_g[i]=random(node_number);
//sel_g[i]=595;
group_color[i]=group_color[i];
flag_gorup[i]=0;
Form1->Image2->Canvas->Brush->Style=bsSolid;
Draw_Node(Form1->Image2,"Pen",clRed,2,sel_g[i]);
Form1->Edit_Head->Text=Form1->Edit_Head->Text+IntToStr(sel_g[i])+"{"+IntToStr(node[sel_g[i]].coordinate_x)+" , "+IntToStr(node[sel_g[i]].coordinate_y)+"} ";
}
for(int i=0;i<group_number;i++)
{
childHC=0;
FindGroupFlooding(sel_g[i],sel_g[i],i); // FindGroupFlooding(int ParentID , int HeadID , int GroupID)
flag_gorup[i]=1;
}
//grouping
int min_hc,min_group;
for(int i=0;i<node_number;i++)
{
min_hc=node[i].to_each_head_hop_count[0];
min_group=0;
for(int j=1;j<group_number;j++)
{
if(min_hc>node[i].to_each_head_hop_count[j])
{
min_hc=node[i].to_each_head_hop_count[j];
min_group=j;
node[i].Group_ID=j;
}
}
}
for(int i=0;i<node_number;i++)
{
for(int j=0;j<group_number;j++)
{
node[i].ParentID=node[i].to_head_parent[node[i].Group_ID];
node[node[i].to_head_parent[node[i].Group_ID]].ChildrenID.push_back(i);
}
}
for(int i=0;i<node_number;i++)
{
TListItem *item=Form1->ListView2->Items->Add();
item->Caption=IntToStr(i);
item->SubItems->Add(IntToStr(node[i].coordinate_x));
item->SubItems->Add(IntToStr(node[i].coordinate_y));
item->SubItems->Add(IntToStr(node[i].Group_ID));
Form1->Image2->Canvas->Brush->Style=bsSolid;
Draw_Node(Form1->Image2,"Pen",group_color[node[i].Group_ID],2,i);
Form1->Image2->Canvas->Pen->Color=clBlack;
Form1->Image2->Canvas->MoveTo(node[i].coordinate_x+communication_range,node[i].coordinate_y+communication_range);
Form1->Image2->Canvas->LineTo(node[node[i].ParentID].coordinate_x+communication_range,node[node[i].ParentID].coordinate_y+communication_range);
TColor color;
if(node[i].ChildrenID.size()==0)
{
Form1->Image2->Canvas->Brush->Style=bsSolid;
color=RGB(61,250,5);
Draw_Node(Form1->Image2,"Brush",color,2,i);
node[i].isLeaf=true;
}
else
{
Form1->Image2->Canvas->Brush->Style=bsSolid;
Draw_Node(Form1->Image2,"Brush",clBlack,2,i);
node[i].isLeaf=false;
}
}
Determine_Testing_Node();
// Show Testing Node
for(int i=0;i<node_number;i++)
{
if(node[i].isTestingNode)
{
Form1->Image2->Canvas->Brush->Style=bsSolid;
Draw_Node(Form1->Image2,"Brush",clRed,2,i);
}
}
for(int i=0;i<group_number;i++)
Draw_Node(Form1->Image2,"Pen",clRed,4,sel_g[i]);
}
//---------------------------------------------------------------------------
void BoundaryDetection::FindCycle()
{
// (2-hop , 1-hop) set sorting
for(int i=0;i<node_number;i++)
{
node[i].sets=new Two_Hop_Set[200];
for(int j=0;j<node[i].Two_Hop_ID.size();j++)
{
int flag=0;
for(int k=0;k<node[node[i].Two_Hop_ID[j]].One_Hop_ID.size();k++)
{
for(int m=0;m<node[i].One_Hop_ID.size();m++)
{
if(node[node[i].Two_Hop_ID[j]].One_Hop_ID[k]==node[i].One_Hop_ID[m])
{
node[i].sets[0].id=node[i].Two_Hop_ID[j];
node[i].sets[0].One_Hop_Set.push_back(node[i].One_Hop_ID[m]);
flag=1;
}
}
}
if(flag==1)
node[i].Tmp_Two_Hop_Set.push_back(node[i].sets[0]);
node[i].sets[0].One_Hop_Set.clear();
}
}
for(int i=0;i<node_number;i++)
{
for(int j=0;j<node[i].Tmp_Two_Hop_Set.size();j++)
{
sort(node[i].Tmp_Two_Hop_Set.begin(),node[i].Tmp_Two_Hop_Set.end(),sort_id);
for(int k=0;k<node[i].Tmp_Two_Hop_Set[j].One_Hop_Set.size();k++)
{
sort(node[i].Tmp_Two_Hop_Set[j].One_Hop_Set.begin(),node[i].Tmp_Two_Hop_Set[j].One_Hop_Set.end());
node[i].Tmp_Two_Hop_Set[j].One_Hop_Set.erase(unique(node[i].Tmp_Two_Hop_Set[j].One_Hop_Set.begin(), node[i].Tmp_Two_Hop_Set[j].One_Hop_Set.end()), node[i].Tmp_Two_Hop_Set[j].One_Hop_Set.end());
}
}
for(int j=0;j<node[i].Tmp_Two_Hop_Set.size();j++)
{
node[i].sets[0].id=node[i].Tmp_Two_Hop_Set[j].id;
node[i].sets[0].One_Hop_Set=node[i].Tmp_Two_Hop_Set[j].One_Hop_Set;
node[i].sets[0].One_Hop_Count=node[i].Tmp_Two_Hop_Set[j].One_Hop_Set.size();
node[i].All_Two_Hop_Set.push_back(node[i].sets[0]);
node[i].sets[0].One_Hop_Set.clear();
}
sort(node[i].All_Two_Hop_Set.begin(),node[i].All_Two_Hop_Set.end(),sort_hop_count);
for(int j=0;j<node[i].All_Two_Hop_Set.size();j++)
{
if(node[i].All_Two_Hop_Set[j].One_Hop_Count>1)
node[i].Reduce_Two_Hop_Set.push_back(node[i].All_Two_Hop_Set[j]);
}
}
Application->ProcessMessages();
for(int i=0;i<node_number;i++)
{
if(node[i].Reduce_Two_Hop_Set.size()>0)
{
node[i].Min_Two_Hop_Set.push_back(node[i].Reduce_Two_Hop_Set[0]);
for(int j=1;j<(int)node[i].Reduce_Two_Hop_Set.size();j++)
if(!Check_Subset(node[i].Reduce_Two_Hop_Set, node[i].Min_Two_Hop_Set, j))
node[i].Min_Two_Hop_Set.push_back(node[i].Reduce_Two_Hop_Set[j]);
for(int j=0;j<(int)node[i].Min_Two_Hop_Set.size();j++)
{
for(int k=0;k<node[i].Min_Two_Hop_Set[j].One_Hop_Count;k++)
{
for(int m=0;m<(int)node[i].Min_Two_Hop_Set.size();m++)
{
if(j!=m)
{
vector<int>::iterator it =
find(node[i].Min_Two_Hop_Set[m].One_Hop_Set.begin(), node[i].Min_Two_Hop_Set[m].One_Hop_Set.end(), node[i].Min_Two_Hop_Set[j].One_Hop_Set[k]);
if(it != node[i].Min_Two_Hop_Set[m].One_Hop_Set.end())
{
node[i].Min_Two_Hop_Set[j].Two_Hop_Link.push_back (node[i].Min_Two_Hop_Set[m].id);
node[i].Min_Two_Hop_Set[j].Two_Hop_Index.push_back(m);
}
}
}
}
sort(node[i].Min_Two_Hop_Set[j].Two_Hop_Link.begin(),node[i].Min_Two_Hop_Set[j].Two_Hop_Link.end());
node[i].Min_Two_Hop_Set[j].Two_Hop_Link.erase(unique(node[i].Min_Two_Hop_Set[j].Two_Hop_Link.begin(), node[i].Min_Two_Hop_Set[j].Two_Hop_Link.end()),
node[i].Min_Two_Hop_Set[j].Two_Hop_Link.end());
sort(node[i].Min_Two_Hop_Set[j].Two_Hop_Index.begin(),node[i].Min_Two_Hop_Set[j].Two_Hop_Index.end());
node[i].Min_Two_Hop_Set[j].Two_Hop_Index.erase(unique(node[i].Min_Two_Hop_Set[j].Two_Hop_Index.begin(), node[i].Min_Two_Hop_Set[j].Two_Hop_Index.end()),
node[i].Min_Two_Hop_Set[j].Two_Hop_Index.end());
}
if(group_number>1)
{
Determine_Boundary_Node_1(i);
}
else if(group_number==1)
{
Determine_Boundary_Node_2(i);
}
}
}
Application->ProcessMessages();
for(int i=0;i<node_number;i++)
{
if(node[i].status=="boundary")
Find_Other_Boundary_Node(i);
}
Draw_Node();
//Prune_Boundary();
for(int i=0;i<node_number;i++)
{
if(node[i].status=="boundary" && node[i].isAddToPath==false)
{
node[i].isAddToPath=true;
Count_Boundary(i,i);
}
}
Count_Ancestor();
Count_Local_Minimum_Number();
Application->ProcessMessages();
vector<int> Boundary_Node_Set;
for(int i=0;i<node_number;i++)
if(node[i].status=="boundary")
Boundary_Node_Set.push_back(i);
}
//---------------------------------------------------------------------------
void BoundaryDetection::Determine_Boundary_Node_1(int i)
{
if( (node[i].Min_Two_Hop_Set.size() <=thresold || node[i].One_Hop_ID.size()<=thresold) && node[i].isTestingNode==true )
{
Application->ProcessMessages();
node[i].status="boundary";
}
if(node[i].Min_Two_Hop_Set.size()>thresold && node[i].isTestingNode==true)
{
if(node[i].Min_Two_Hop_Set.size()>0)
{
if(node[i].Min_Two_Hop_Set[0].Two_Hop_Index.size()>0)
{
Graph G;
int src=0;
int des;
des=node[i].Min_Two_Hop_Set[0].Two_Hop_Index[0];
Path path;
Marking visited;
G.NodeCount=node[i].Min_Two_Hop_Set.size();
for(int m=0;m<G.NodeCount;m++)
for(int n=0;n<G.NodeCount;n++)
G.AdjMatrix[m][n]=0;
for(int m=0;m<G.NodeCount;m++)
{
visited[m]=false;
for(int n=0;n<G.NodeCount;n++)
for(int k=0;k<node[i].Min_Two_Hop_Set[m].Two_Hop_Index.size();k++)
G.AdjMatrix[m][node[i].Min_Two_Hop_Set[m].Two_Hop_Index[k]]=1;
}
SearchAllPath(i,G,path,visited,src,des,1);
Get_Max_Cycle_Path(i);
if(node[i].status!="boundary")
{
if(node[i].max_cycle_path.size()>thresold)
{
Prune_Cycle_Path(i);
if(node[i].cycle_path.size()>thresold)
{
node[i].status="not boundary";
}
else
{
node[i].isTesting=true;
total_testing_node++;
node[i].status="boundary";
}
}
else
{
node[i].isTesting=true;
total_testing_node++;
node[i].status="boundary";
}
}
if(node[i].status=="boundary")
{
node[i].isTesting=true;
total_testing_node++;
node[i].status="boundary";
}
}
else
{
node[i].isTesting=true;
total_testing_node++;
node[i].status="boundary";
}
}
else
{
node[i].isTesting=true;
total_testing_node++;
node[i].status="boundary";
}
}
}
//---------------------------------------------------------------------------
void BoundaryDetection::Determine_Boundary_Node_2(int i)
{
if( node[i].Min_Two_Hop_Set.size() <=thresold || node[i].One_Hop_ID.size()<=thresold )
{
Application->ProcessMessages();
node[i].status="boundary";
}
if(node[i].Min_Two_Hop_Set.size()>thresold )
{
if(node[i].Min_Two_Hop_Set.size()>0)
{
if(node[i].Min_Two_Hop_Set[0].Two_Hop_Index.size()>0)
{
Graph G;
int src=0;
int des;
des=node[i].Min_Two_Hop_Set[0].Two_Hop_Index[0];
Path path;
Marking visited;
G.NodeCount=node[i].Min_Two_Hop_Set.size();
for(int m=0;m<G.NodeCount;m++)
for(int n=0;n<G.NodeCount;n++)
G.AdjMatrix[m][n]=0;
for(int m=0;m<G.NodeCount;m++)
{
visited[m]=false;
for(int n=0;n<G.NodeCount;n++)
for(int k=0;k<node[i].Min_Two_Hop_Set[m].Two_Hop_Index.size();k++)
G.AdjMatrix[m][node[i].Min_Two_Hop_Set[m].Two_Hop_Index[k]]=1;
}
SearchAllPath(i,G,path,visited,src,des,1);
Get_Max_Cycle_Path(i);
if(node[i].status!="boundary")
{
if(node[i].max_cycle_path.size()>thresold)
{
Prune_Cycle_Path(i);
if(node[i].cycle_path.size()>thresold)
{
node[i].status="not boundary";
}
else
{
node[i].isTesting=true;
total_testing_node++;
node[i].status="boundary";
}
}
else
{
node[i].isTesting=true;
total_testing_node++;
node[i].status="boundary";
}
}
}
else
{
node[i].isTesting=true;
total_testing_node++;
node[i].status="boundary";
}
}
else
{
node[i].isTesting=true;
total_testing_node++;
node[i].status="boundary";
}
}
}
//---------------------------------------------------------------------------
bool BoundaryDetection::Check_Subset(vector<Two_Hop_Set> source, vector<Two_Hop_Set> dist, int index)
{
int flag=0;
for(int i=0;i<(int)dist.size();i++)
if(includes(dist[i].One_Hop_Set.begin(),dist[i].One_Hop_Set.end(),source[index].One_Hop_Set.begin(),source[index].One_Hop_Set.end()))
flag=1;
if(flag==0)
return false;
else if(flag==1)
return true;
}
//---------------------------------------------------------------------------
void BoundaryDetection::PrintPath(int id,Path& path, int length)
{
AnsiString tt="";
vector<int> i_path;
for(int i=0;i<length;i++)
{
i_path.push_back(path[i]);
tt+=IntToStr(path[i])+" ";
//Form1->Memo1->Lines->Text=Form1->Memo1->Lines->Text+IntToStr(path[i])+" ";
}
node[id].all_cycle_path.push_back(i_path);
Form1->Memo4->Lines->Add(IntToStr(id)+"\t"+tt);
}
//---------------------------------------------------------------------------
void BoundaryDetection::SearchAllPath(int id,const Graph& G, Path& path, Marking& visited, int v, int des, int length)
{
if(visited[v])
return;
path[length-1]=v;
if(v==des)
{
//if(length>3)
PrintPath(id,path,length);
}
else
{
visited[v]=true;
for(int i=0;i<G.NodeCount;i++)
if(G.AdjMatrix[v][i]!=0 && !visited[i])
SearchAllPath(id,G,path,visited,i,des,length+1);
visited[v]=false;
}
}
//---------------------------------------------------------------------------
void BoundaryDetection::Get_Max_Cycle_Path(int id)
{
int max_len;
int max_index=0;
try
{
if(node[id].all_cycle_path[0].size()>0)
{
max_len=node[id].all_cycle_path[0].size();
for(int j=1;j<node[id].all_cycle_path.size();j++)
{
if(max_len<node[id].all_cycle_path[j].size())
{
max_len=node[id].all_cycle_path[j].size();
max_index=j;
}
}
for(int j=0;j<node[id].all_cycle_path[max_index].size();j++)
node[id].max_cycle_path=node[id].all_cycle_path[max_index];
}
if(node[id].all_cycle_path[0].size()==0)
node[id].status="boundary";
}
catch(...)
{
node[id].status="boundary";
}
}
//---------------------------------------------------------------------------
void BoundaryDetection::Prune_Cycle_Path(int id)
{
node[id].cycle_path=node[id].max_cycle_path;
if(node[id].max_cycle_path.size()<=6)
{
vector<int>remove_node;
for(int i=0;i<node[id].max_cycle_path.size();i++)
{
int cmp_index=(i+2)%node[id].max_cycle_path.size();
if(cmp_index!=1)
{
for(int j=0;j<node[id].Min_Two_Hop_Set.size();j++)
{
if(node[id].Min_Two_Hop_Set[j].id==node[id].Min_Two_Hop_Set[node[id].max_cycle_path.at(i)].id)
{
vector<int>::iterator it=
find(node[id].Min_Two_Hop_Set[j].Two_Hop_Link.begin(),node[id].Min_Two_Hop_Set[j].Two_Hop_Link.end(),
node[id].Min_Two_Hop_Set[node[id].max_cycle_path.at(cmp_index)].id);
if(it != node[id].Min_Two_Hop_Set[j].Two_Hop_Link.end())
{
remove_node.push_back(node[id].max_cycle_path.at(cmp_index));
}
}
}
}
}
if(remove_node.size()>0)
{
for(int i=0;i<remove_node.size();i++)
{
vector<int>::iterator pos= remove(node[id].cycle_path.begin(),node[id].cycle_path.end(),remove_node.at(i));
node[id].cycle_path.erase(pos,node[id].cycle_path.end());
}
}
}
node[id].max_cycle_path=node[id].cycle_path;
if(node[id].max_cycle_path.size()<=6)
{
vector<int>remove_node;
for(int i=0;i<node[id].max_cycle_path.size();i++)
{
int cmp_index=(i+2)%node[id].max_cycle_path.size();
if(cmp_index!=1)
{
for(int j=0;j<node[id].Min_Two_Hop_Set.size();j++)
{
if(node[id].Min_Two_Hop_Set[j].id==node[id].Min_Two_Hop_Set[node[id].max_cycle_path.at(i)].id)
{
vector<int>::iterator it=
find(node[id].Min_Two_Hop_Set[j].Two_Hop_Link.begin(),node[id].Min_Two_Hop_Set[j].Two_Hop_Link.end(),
node[id].Min_Two_Hop_Set[node[id].max_cycle_path.at(cmp_index)].id);
if(it != node[id].Min_Two_Hop_Set[j].Two_Hop_Link.end())
{
remove_node.push_back(node[id].max_cycle_path.at(cmp_index));
}
}
}
}
}
if(remove_node.size()>0)
{
for(int i=0;i<remove_node.size();i++)
{
vector<int>::iterator pos= remove(node[id].cycle_path.begin(),node[id].cycle_path.end(),remove_node.at(i));
node[id].cycle_path.erase(pos,node[id].cycle_path.end());
}
}
}
}
//---------------------------------------------------------------------------
bool BoundaryDetection::ShowPath(int x,int y)
{
for(int i=0;i<node_number;i++)
{
int xx=node[i].coordinate_x+communication_range;
int yy=node[i].coordinate_y+communication_range;
if(x==xx && y==yy)
{
ShowMessage(node[i].status);
ShowMessage(i);
}
}
}
//---------------------------------------------------------------------------
void BoundaryDetection::Find_Other_Boundary_Node(int FromID)
{
for(int i=0;i<node[FromID].One_Hop_ID.size();i++)
{
if(node[node[FromID].One_Hop_ID.at(i)].status=="not test")
{
Determine_Boundary_Node_2(node[FromID].One_Hop_ID.at(i));
if(node[node[FromID].One_Hop_ID.at(i)].status=="boundary")
{
Find_Other_Boundary_Node(node[FromID].One_Hop_ID.at(i));
}
}
}
}
//---------------------------------------------------------------------------
void BoundaryDetection::Draw_Node()
{
for(int i=0;i<node_number;i++)
{
if(node[i].status=="not test")
{
Form1->Image3->Canvas->Font->Size=3;
Form1->Image3->Canvas->TextOutA(node[i].coordinate_x+communication_range-3,node[i].coordinate_y+communication_range-6,"■"); //other node
}
if(node[i].status=="not boundary")
{
Form1->Image3->Canvas->Font->Size=5;
Form1->Image3->Canvas->TextOutA(node[i].coordinate_x+communication_range-3,node[i].coordinate_y+communication_range-6,"▲"); //not boundary node
}
if(node[i].status=="boundary")
{
Form1->Image3->Canvas->Font->Size=5;
Form1->Image3->Canvas->TextOutA(node[i].coordinate_x+communication_range-3,node[i].coordinate_y+communication_range-6,"★"); //boundary node
}
}
}
//---------------------------------------------------------------------------
void BoundaryDetection::Count_Boundary(int FromID,int Ancestor)
{
if(node[FromID].status=="boundary")
{
node[FromID].PathRoot=Ancestor;
for(int i=0;i<node[FromID].One_Hop_ID.size();i++)
{
if(node[node[FromID].One_Hop_ID.at(i)].status=="boundary" && node[node[FromID].One_Hop_ID.at(i)].isAddToPath==false)
{
node[node[FromID].One_Hop_ID.at(i)].PathRoot=Ancestor;
node[node[FromID].One_Hop_ID.at(i)].isAddToPath=true;
Count_Boundary(node[FromID].One_Hop_ID.at(i),Ancestor);
}
}
}
}
//---------------------------------------------------------------------------
void BoundaryDetection::Count_Ancestor()
{
vector<int> Boundary_Count_tmp;
for(int i=0;i<node_number;i++)
{
if(node[i].status=="boundary")
total_boundary_node++;
Boundary_Count_tmp.push_back(node[i].PathRoot);
}
sort(Boundary_Count_tmp.begin(),Boundary_Count_tmp.end());
Boundary_Count_tmp.erase(unique(Boundary_Count_tmp.begin(), Boundary_Count_tmp.end()), Boundary_Count_tmp.end());
for(int i=0;i<Boundary_Count_tmp.size();i++)
{
if(node[Boundary_Count_tmp.at(i)].status=="boundary")
{
Boundary_Count.push_back(Boundary_Count_tmp.at(i));
}
}
TColor *boundary_color;
boundary_color=new TColor[100];
boundary_color[0]=RGB(64,0,64);
boundary_color[1]=RGB(115,115,0);
boundary_color[2]=RGB(255,128,0);
boundary_color[3]=RGB(0,0,255);
randomize();
for(int i=4;i<100;i++)
{
boundary_color[i]=RGB(random(255),random(255),random(255));
}
int bc=Boundary_Count.size();
int *final_boundary=new int[Boundary_Count.size()];
for(int j=0;j<Boundary_Count.size();j++)
final_boundary[j]=0;
for(int i=0;i<node_number;i++)
{
if(node[i].isAddToPath==true) // boundary node
{
for(int j=0;j<Boundary_Count.size();j++)
{
if(node[i].PathRoot==Boundary_Count.at(j))
{
Form1->Image4->Canvas->Font->Size=5;
Form1->Image4->Canvas->Font->Color=boundary_color[j];
Form1->Image4->Canvas->TextOutA(node[i].coordinate_x+communication_range-3,node[i].coordinate_y+communication_range-6,"★"); //boundary nod
Form1->Image7->Canvas->Font->Size=5;
Form1->Image7->Canvas->Font->Color=boundary_color[j];
Form1->Image7->Canvas->TextOutA(node[i].coordinate_x+communication_range-3,node[i].coordinate_y+communication_range-6,"★"); //boundary nod
final_boundary[j]++;
}
}
}
}
vector<int> Count_Boundary_Node;
for(int i=0;i<node_number;i++)
{
if(node[i].isAddToPath==true) // boundary node
{
for(int j=0;j<Boundary_Count.size();j++)
{
if(node[i].PathRoot==Boundary_Count.at(j))
{
if(final_boundary[j]>3)
{
Count_Boundary_Node.push_back(final_boundary[j]);
Form1->Image8->Canvas->Font->Size=5;
Form1->Image8->Canvas->Font->Color=boundary_color[j];
Form1->Image8->Canvas->TextOutA(node[i].coordinate_x+communication_range-3,node[i].coordinate_y+communication_range-6,"★"); //boundary node
}
}
}
}
}
sort(Count_Boundary_Node.begin(),Count_Boundary_Node.end());
Count_Boundary_Node.erase(unique(Count_Boundary_Node.begin(), Count_Boundary_Node.end()), Count_Boundary_Node.end());
Form1->Memo10->Text=Form1->Memo10->Text+"G="+IntToStr(group_number)+"\tTotal Holes:\t"+ IntToStr(Count_Boundary_Node.size()-1);
for(int i=0;i<Count_Boundary_Node.size();i++)
{
Form1->Memo10->Text=Form1->Memo10->Text+"\t"+IntToStr(Count_Boundary_Node.at(i));
}
Form1->Memo10->Lines->Add("");
Form1->Memo10->Lines->SaveToFile(Form1->OpenDialog2->FileName);
total_boundary=Boundary_Count.size();
}
//---------------------------------------------------------------------------
void BoundaryDetection::Count_Local_Minimum_Number()
{
int min_flag;
for(int i=0;i<node_number;i++)
{
min_flag=0;
if(node[i].status=="boundary")
{
for(int j=0;j<node[i].One_Hop_ID.size();j++)
{
if(node[node[i].One_Hop_ID.at(j)].status=="boundary")
if(node[i].Node_ID > node[node[i].One_Hop_ID.at(j)].Node_ID)
min_flag=1;
}
if(min_flag==0)
{
local_minimum_id_count++;
min_str=min_str+IntToStr(i)+" ";
Local_Min_Count.push_back(i);
}
}
}
for(int k=0;k<Local_Min_Count.size();k++)
{
Form1->Image7->Canvas->Font->Size=5;
Form1->Image7->Canvas->Font->Color=clRed;
Form1->Image7->Canvas->TextOutA(node[Local_Min_Count.at(k)].coordinate_x+communication_range-3,node[Local_Min_Count.at(k)].coordinate_y+communication_range-6,"★"); //boundary nod
Form1->Image7->Canvas->TextOutA(node[Local_Min_Count.at(k)].coordinate_x,node[Local_Min_Count.at(k)].coordinate_y,IntToStr(Local_Min_Count.at(k))); //boundary nod
}
}
//---------------------------------------------------------------------------